leetcode-n数之和

蓝星 2020年01月04日 334次浏览

“N数之和”算leetcode算法中比较经典的算法,包括第15题的“三数之和”,16题的“最接近的三数之和”及18题的“四数之和”。其实这些题都可以总结为“N数之和”,其解题思路都是一样的。 本文将以最简单的“三数之和”介绍这类题的解题思路

题目描述

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0
找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

题目中要求判断是否存在三个元素(a, b, c),使得三个元素之和为0。而我们比较熟悉的是寻找两个元素(a, b),使a+b=0。对于两个元素的,我们可以将数组先进行排序,然后使用“首尾双指针”的方法获取a和b的值。同理,当需要判断三个元素和为0时,问题就转化为两个元素(a,b)的和是否等于另一个元素的负值(0-c)。因此我们可以将问题进行简化

  1. 对于有序数组,寻找三个元素的和为0,a+b+c=0;
  2. 对于有序数组,已知数组某个位置的一个数(c),判断数组中是否存在其他两个元素(a, b),使得a+b+c=0;

具体算法

image

由于数组是无序的,所以我们可以先对其进行排序(对于N数之和,其时间复杂度大部分都消耗在数组的循环上,所以排序产生的时间复杂度(nlogn)可以忽略)。然后通过遍历数组来获取和尾0的三个数。

  1. 固定index,寻找除了index之外i和j的位置,使得nums[index]+nums[i]+nums[j]=0
  2. 对于index后的数,使用首尾双指针的方法得到满足条件的i和j。

具体代码如下:

public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int index = 0; index < nums.length - 2; ++index){
            //跳过index重复的
            if (index > 0 && nums[index] == nums[index - 1]){
                continue;
            }
            int i = index + 1, j = nums.length - 1;
            while (i < j){
                //跳过i重复的
                if (i > index + 1 && nums[i] == nums[i - 1]){
                    i++;
                    continue;
                }
                //跳过j重复的
                if (j < nums.length - 1 && nums[j] == nums[j + 1]){
                    j--;
                    continue;
                }
                int tmpValue = nums[index] + nums[i] + nums[j];
                if (tmpValue == 0){
                    List<Integer> tmpResult = new ArrayList<>();
                    tmpResult.add(nums[index]);
                    tmpResult.add(nums[i]);
                    tmpResult.add(nums[j]);
                    result.add(tmpResult);
                    i++;
                    j--;
                }else if (tmpValue > 0){
                    j--;
                }else {
                    i++;
                }
            }
        }
        return result;
    }

需要注意的点:

  1. 因为需要找三数之和,所以index不需要遍历到数组末尾,只需要遍历到nums.length - 3的位置即可
  2. 由于不需要重复的数,所以index再向后移动的过程中需要判断是否已经取过该数,同理i向后移动和j向前移动的时候也需要判断是否重复。

扩展

对于第16题“最接近的三树之和”,只需要判断tmpValue和target的绝对值是否是最小的即可

int tmpV = nums[index] + nums[i] + nums[j];
int tmpAbs = Math.abs(tmpV - target);
if (tmpAbs < abs){
    result = tmpV;
    abs = tmpAbs;
}
if (abs == 0){
    return result;
}
if (tmpV < target){
    i++;
}else {
    j--;
}

对于18题的“四数之和”,同理可以使用“三树之后”的方法解决,只不过需要增加一层for循环

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4){
            return result;
        }
        Arrays.sort(nums);
        for (int index1 = 0; index1 < nums.length - 3; ++index1){
            if (index1 > 0 && nums[index1] == nums[index1 - 1]){
                continue;
            }
            for (int index2 = index1 + 1; index2 < nums.length - 2; ++index2) {
                if (index2 > index1 + 1 && nums[index2] == nums[index2 - 1]) {
                    continue;
                }
                int i = index2 + 1, j = nums.length - 1;
                while (i < j) {
                    if (i > index2 + 1 && nums[i] == nums[i - 1]) {
                        i++;
                        continue;
                    }
                    if (j < nums.length - 1 && nums[j] == nums[j + 1]) {
                        j--;
                        continue;
                    }
                    int tmpResult = nums[index1] + nums[index2] + nums[i] + nums[j];
                    if (tmpResult == target) {
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[index1]);
                        tmp.add(nums[index2]);
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        result.add(tmp);
                    }
                    if (tmpResult < target) {
                        i++;
                    } else {
                        j--;
                    }
                }
            }
        }
        return result;
    }