力扣labuladong一刷day12拿下N数之和问题共4题

力扣labuladong一刷day12拿下N数之和问题共4题

首先我再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

一、1. 两数之和

题目链接：https://leetcode.cn/problems/two-sum/
思路：使用hashmap存放遍历过的元素，只要target-nums[i]存在即可返回

class Solution {
   public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int t = target-nums[i];
            if (map.containsKey(t)) {
                return new int[]{map.get(t), i};
            }else {
                map.put(nums[i], i);
            }
        }
        return new int[]{};
    }
}

二、15. 三数之和

题目链接：https://leetcode.cn/problems/3sum/
思路：每一部分都需要去重，a,b,c 三个数，-a = b+c 这就把3数之和变成了2数之和，a每前进一步，b和c都要把[a+1, len-1]的区间内寻找和为-a的两个数，当然因为排序过了，每一个数使用时都要去重，如果出现过就跳过。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> arrayLists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            if (i>0 && nums[i] == nums[i-1]) continue;
            int j = i+1, k = nums.length-1;
            while (j < k) {
                int t = nums[i]+nums[j]+nums[k];
                if (t == 0) {
                    arrayLists.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j<k && nums[j] == nums[j+1])j++;
                    while (j<k && nums[k] == nums[k-1])k--;
                    j++;
                    k--;
                }else if (t > 0) {
                    k--;
                }else {
                    j++;
                }
            }
        }
        return arrayLists;
    }
}

三、167. 两数之和 II - 输入有序数组

题目链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
思路：左右双子针。

class Solution {
   public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length-1;
        while (i<j) {
            int t = numbers[i]+numbers[j];
            if (t == target) return new int[]{i+1, j+1};
            else if (t > target) {
                j--;
            }else {
                i++;
            }
        }
        return new int[]{-1, -1};
    }
}

四、18. 四数之和

题目链接：https://leetcode.cn/problems/4sum/
思路：和上面的3数之和一样，当然还有去重和早停

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> arrayLists = new ArrayList<>();
        if (nums.length<4) return arrayLists;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < nums.length-2; j++) {
                if (nums[i] + nums[j] > target && nums[i] > 0) break;
                if (j > i+1 && nums[j] == nums[j-1])continue;
                int k = j+1, v = nums.length-1;
                while (k < v) {
                    long t =(long) nums[i]+nums[j]+nums[k]+nums[v];
                    if (t == target) {
                        arrayLists.add(Arrays.asList(nums[i], nums[j], nums[k], nums[v]));
                        while (k<v && nums[k] == nums[k+1]) k++;
                        while (k<v && nums[v] == nums[v-1]) v--;
                        k++;
                        v--;
                    }else if (t > target) {
                        v--;
                    }else {
                        k++;
                    }
                }
            }
        }
        return arrayLists;
    }
}