LeetCode 1：两数之和

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 205

思路：

数组不是单调递增，若先Arrays.sort(nums) 排序，则排序后索引会变化 ！

① 确定一个数nums[i] ② 找另一个数（target-nums[i]）

方法一：暴力枚举

注意内层for范围是 j = i +1 开始到 n，若 j 也从0开始则会出现两个索引重复的情况，且会重复遍历之前已经搜索过的元素

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 暴力法
        int n=nums.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[j]+nums[i]==target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }
}

时间复杂度：O(N^2)
空间复杂度：O(1)

方法二：利用Hash表

先考虑HashMap的键值对怎么存：HashMap的get()是由key得到value，所以让数组元素的值作为key，索引作为value
比较的是当前nums[i]和之前存入的数！而两个for比较的是nums[i]和 [nums[i+1]，nums[n-1] ]
当HashMap中存在 target – nums[i] 时，使用get方法获取索引
和数组中重复的数字一样，一定要好先判断再存值，不然可能索引重复 ，若是先存再判断，第 i 次存入的可能刚好满足条件，则索引为两个 i

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> h=new HashMap<>(); // 存索引和值
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(h.containsKey(target-nums[i])){ // 先判断再存，不然就可能索引重复
                int j=h.get(target-nums[i]);  // 由key得到value索引
                return new int[] {i,j};
            }
            h.put(nums[i],i);
        }
        return new int[0];
    }
}