leetcode力扣——一篇文章解决多数之和问题

 

目录

1、两数之和

2、三数之和

3、最接近的三数之和

4、四数之和

1、两数之和

1.两数相加

题目描述：

 思路：这道题很简单，我们就不讲暴力匹配了；我们都知道Map集合有一个的自带方法containsKey(key),这个方法是来判断map集合中是否有该key值，小伙伴们听到着是不是觉得豁然开朗，这不就是为这道两数相加而创造的吗哈哈

话不多说，咱们直接上代码：

 public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
        //如果存在key值，则返回value(代表索引) 
            if (map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }

时间复杂度：O(n)

空间复杂度：O(n)

2、三数之和

15.三数之和

题目描述：

思路：题目意思是要我们在数组找到三个不重复元素相加等于0，既然三个数相加，自然而然我们想到了双指针法，固定一个元素 i，移动另外两个元素 left 和 right，left=0，right=nums.length -1，sum = nums[i] + nums[left] + nums[right]；

至于移动的条件，我们可以先把数组排序得到一个有序数组，再进行三种情况判断

当 sum>0，咱们数组是有序数组，证明right大了，可以向左移，right--；

当 sum<0时，我们就left++；

当sum=0 的时候我们就把值存入集合内。

有了这个思路我们不多说，直接上代码：

 public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        if (nums.length <3) return lists;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            //因为数组是排序好的，所以当nums[i]大于0时，可以直接退出循环
            if (nums[i] > 0) break; 
            //当前一个值与当前值相等时，直接跳过去除重复解
            if (i > 0 && nums[i] == nums[i-1]) continue;i
            int left = i+1;
            int right = nums.length -1;
            while (left<right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    //当nums[left] == nums[left+1]时，多移动一次left，去除重复解
                    while (left<right && nums[left] == nums[left+1]) left++;
                    while (left<right && nums[right] == nums[right-1]) right--;
                    left++;
                    right --;
                }
                else if (sum > 0) right--;
                else left++;
            }
        }
        return lists;
    }

时间复杂度：由于加入了循环，O(n^2+nlogn)

空间复杂度：题目要求的返回值类型是List<List<Integer>>,所以无法优化都是O(m*n)

3、最接近的三数之和

16.最接近的三数之和

题目描述：

思路： 这道题与上一道三数之和有异曲同工之妙，都是求三数之和，只不过这道题是要求一个三数之和最接近target的数，我们可以利用上一道题的思维，依旧是双指针法，固定一个元素 i，移动另外两个元素 left 和 right，left=0，right=nums.length -1；

与上一道题不同的是，我们可能在数组中得到三数相加等于target的数，也可能得不到，这就出现最接近这个概念，得到了等于target就简单，我们直接返回target就行；若是没有我们就需要引入一个变量close，用它来表示最接近target的值，同时还要不断地进行判断，当|target-close|>|target-sum|时，证明此时三数之和更接近，每遍历一次，判断一次，直到循环结束。

代码如下：

public int threeSumClosest(int[] nums, int target) {
        int close = -1000;
        for (int i = 0; i < nums.length-2; i++) {
            //当前一个值与当前值相等时，直接跳过去除重复解
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i+1;
            int right = nums.length -1;

            while (left < right){
                int sum = nums[i] + nums[left] +nums[right];
                if (sum == target) return target;
                if (sum > target) right--;
                if (sum < target) left++;
                int x = Math.abs(target-close);
                int y = Math.abs(target-sum);
                if (x > y) close = sum;
            }
        }
        return close;
    }

时间复杂度：O(n^2)

空间复杂度：O(1)

4、四数之和

18.四数之和

题目描述：

思路： 又是一道多数相加问题，和三数相加可以说是换汤不换药，三数之和我们利用了双指针法，四数之和我们照样利用，无非是多嵌套一层for循环，固定好两个值；

我们直接上代码：

 public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        if (nums.length < 4) return lists;
        Arrays.sort(nums);
        int left, right, sum;
        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 (j > i + 1 && nums[j] == nums[j - 1]) continue;
                left = j + 1;
                right = nums.length - 1;
                while (left < right) {
                    sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        lists.add(list);
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum > target) right--;
                    else left++;
                }
            }
        }
        return lists;
    }

时间复杂度：O(n^3+nlogn)

空间复杂度：O(m*n)

总结：多数之和问题虽然不是很难，但我们可以把它吃透，只要理解了这种方法，以后不管是几数相加我们都可以轻松拿捏！