三数之和

题目(LeetCode #15)

给你一个包含 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 的所有情况且不能重复，若直接遍历时间复杂度为 O(N³) ，本题的关键在于如何降低时间复杂度和去除重复解。

可采用双指针法来实现遍历的不重不漏，首先将数组进行排序，再使L 指向 i+1 ，R 指向末尾元素，两指针向中间移动直至相遇为止。在遍历过程中

• 若 nums[i] 与 nums[i-1] 、nums[L] 与 nums[L+1] 、nums[R] 与 nums[R-1] 相等即说明遇到了重复元素，跳过即可；
• 若 nums[i] + nums[L] + nums[R] == target ，即为一组解，L 和 R 同时移动；
• 若 nums[i] + nums[L] + nums[R] > target ，R 应向左移动以减小三数之和；
• 若 nums[i] + nums[L] + nums[R] < target ，L 应向右移动以增大三数之和。

时间复杂度

• 时间复杂度：O(N²) ，数组排序 O(NlogN) ，遍历数组 O(N) ，双指针遍历 O(N) ，总体为 O(NlogN) + O(N) * O(N) ，O(N²)
• 空间复杂度：O(1)

参考题解：LeetCode

Java

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int listLen = nums.length;
        List<List<Integer>> results = new ArrayList<>();
        if (listLen < 3) return results;

        Arrays.sort(nums);
        int L, R;

        for (int i = 0; i < listLen; i++) {
            if (nums[i] > 0) return results;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            L = i + 1;
            R = listLen - 1;
            while (L < R) {
                if (nums[i] + nums[L] + nums[R] == 0) {
                    results.add(new ArrayList<>(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 (nums[i] + nums[L] + nums[R] > 0) {
                    R--;
                } else {
                    L++;
                }
            }
        }

        return results;
    }
}

Python

class Solution:
    def threeSum(self, nums: list) -> list:
        list_len = len(nums)
        results = []
        if not nums or list_len < 3: return results

        nums.sort()
        for i in range(list_len):
            if nums[i] > 0: return results
            if (i > 0 and nums[i] == nums[i - 1]): continue
            L = i + 1
            R = list_len - 1
            while L < R:
                if nums[i] + nums[L] + nums[R] == 0:
                    results.append([nums[i], nums[L], nums[R]])
                    while L < R and nums[L] == nums[L + 1]: L += 1
                    while L < R and nums[R] == nums[R - 1]: R -= 1
                    L += 1
                    R -= 1
                elif nums[i] + nums[L] + nums[R] > 0:
                    R -= 1
                else:
                    L += 1
        return results

Go

package main

import (
    "sort"
)

func threeSum(nums []int) [][]int {
    arrLen := len(nums)
	var results [][]int
	if nums == nil || arrLen < 3 {
		return results
	}

	sort.Ints(nums)

	for i := 0; i < arrLen; i++ {
		if nums[i] > 0 {
			return results
		}

		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		L, R := i+1, arrLen-1
		for L < R {
			if nums[i]+nums[L]+nums[R] == 0 {
				results = append(results, []int{nums[i], nums[L], nums[R]})
				for L < R && nums[L] == nums[L+1] {
					L++
				}
				for L < R && nums[R] == nums[R-1] {
					R--
				}
				L++
				R--
			} else if nums[i]+nums[L]+nums[R] > 0 {
				R--
			} else {
				L++
			}
		}
	}

	return results
}