【LeetCode】1. 两数之和(Set＜＞,int[]转换)

今日学习的文章链接和视频链接

leetcode题目地址：1. 两数之和

?代码随想录题解地址：代码随想录

题目简介

给定一个整数数组?nums?和一个整数目标值?target，请你在该数组中找出?和为目标值?target? 的那?两个?整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

看到题目的第一想法(可以贴代码）

1. 将数组存成Set，每次遍历数组中的每一个元素temp，看看Set里是否contains(target - temp.val)，用ArrayList存结果（结果长度不确定），再转为int[]。

public int[] twoSum(int[] nums, int target) {
    Integer[] arrInteger = Arrays.stream(nums).boxed().toArray(Integer[]::new);
    Set<Integer> s = Arrays.stream(arrInteger).collect(Collectors.toSet());
    ArrayList<Integer> res = new ArrayList<>();

    for (int i = 0; i < nums.length; i++){
        if (s.contains(target-nums[i]) && nums[i] != target/2){
            res.add(i);
            for (int j = i + 1; j < nums.length; j++){
                if (nums[j] == (target-nums[i])){
                    res.add(j);
                    int[] res2 = res.stream().mapToInt(Integer::valueOf).toArray();
                    return res2;
                }
            }
        }
    }
    ArrayList<Integer> res0 = new ArrayList<>();
    for (int i = 0; i < nums.length; i++){
        if (s.contains(target-nums[i])){
            res0.add(i);
            for (int j = i + 1; j < nums.length; j++){
                if (nums[j] == (target-nums[i])){
                    res0.add(j);
                    int[] res2 = res0.stream().mapToInt(Integer::valueOf).toArray();
                    return res2;
                }
            }
        }
    }
    return null;
}

精简了一下之后：

会想起最后return的必为长度为2的数组，直接用int[2]来定义，并删去了一个值可能被用两次的情况（即某数为target的一半），只需要第二个数从当前的下一个元素，而不是当前元素开始遍历即可。

public int[] twoSum(int[] nums, int target) {
    Integer[] arrInteger = Arrays.stream(nums).boxed().toArray(Integer[]::new);
    Set<Integer> s = Arrays.stream(arrInteger).collect(Collectors.toSet());
    int[] res = new int[2];
    for (int i = 0; i < nums.length; i++){
        if (s.contains(target-nums[i])){
            res[0] = i;
            for (int j = i + 1; j < nums.length; j++){
                if (nums[j] == (target-nums[i])){
                    res[1] = j;
                    return res;
                }
            }
        }
    }
    return null;
}

实现过程中遇到哪些困难

无

看完代码随想录之后的想法

【解题思路】使用哈希表里的Map，因为要获取元素值+元素的下标（key-value正好合适），Key用来定义不会重复的属性。

【想法】

1. 第一时间想到哈希表相关的数据结构：找是否出现过某一个元素（及其下标）

2. Map能在最快的时间内根据Key去查找Key是否出现过。

看完视频自己写的ACC：

Map<Integer,Integer> map = new HashMap<>();
int[] res = new int[2];
for (int i = 0; i < nums.length; i++){
    if (!map.containsKey(target-nums[i])){
        map.put(nums[i], i);
    }else{
        res[0] = i;
        res[1] = map.get(target-nums[i]);
        return res;
    }
}
return null;

学习时长

分时间段写的，不记录了。

---

今日收获

1. 【Java中什么集合查询最快】

arraylist size 50000
linkedlist size 50000
map size 50000
set size 50000
----------------------------
arraylist time 49328
linkedlist time 57641
map time 625
set time 578

2. set与int[]转换：

Set<Integer>转int[]

int[] arr = set.stream().mapToInt(Integer::intValue).toArray();

int[]转Set<Integer>

Integer[] arrInteger = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Set<Integer> set = Arrays.stream(arrInteger).collect(Collectors.toSet());