LeetCode高频算法面试题 - 015 - 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题目难度: ★★★, 中等

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

解题思路

• 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[left] 和 nums[right]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
• 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
• 如果 nums[i] = nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
• 当 sum = 0 时，nums[left] = nums[left+1] 说明结果重复，应该跳过left+1，left++
• 当 sum = 0 时，nums[right] = nums[right−1] 说明结果重复，应该跳过right-1，right--
• 当 sum < 0 时, 移动left, left++
• 当 sum > 0 时, 移动right, right--
• 时间复杂度：O(n^2)，n 为数组长度

这题的重点是要先排序，排序后在遍历，可以降低时间复杂度。

代码实现

tips: 以下代码是使用Go代码实现的不同解法, 文章最后可以看C++、C、Java、Python实现

func threeSum(nums []int) [][]int {
  result := make([][]int, 0)
  length := len(nums)
  if length < 3 {
    return result
  }

  sort.Ints(nums)
  i := 0
  for{
    if i >= length-2{
      break
    }
    if nums[i] > 0 {
      break
    }
    if i > 0 && nums[i] == nums[i-1]{
      i += 1
      continue
    }
    left := i +1
    right := length - 1

    for {
      if left >= right{
        break
      }
      sum := nums[i] + nums[left] + nums[right]

      if sum == 0{
        result = append(result, []int{nums[i], nums[left], nums[right]})
        for {
          if left < right && nums[left] == nums[left+1]{
            left += 1
          }else{
            left += 1
            break
          }

        }

        for{
          if left < right && nums[right] == nums[right-1]{
            right -=1
          }else{
            right -= 1
            break
          }
        }
      }

      if sum < 0{
        left += 1
      }

      if sum > 0{
        right -= 1
      }
    }

    i += 1
  }

  return result
}

其他语言版本实现

1、Java

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;
    }
}

2、Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

3、Python3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

4、C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

不用语言版本运行情况对比

也欢迎关注我的公众号: 漫步coding。 一起交流, 在coding的世界里漫步。