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

2023-12-16 11:35:23

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

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());

文章来源:https://blog.csdn.net/Leonardo_t/article/details/134906747
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。