力扣题解最佳实践  >  哈希表  >  15. 三数之和  >  已用 Python, Ruby, Go, C++, JavaScript, C#, Java 语言实现  >  转发 或 贡献代码

    力扣链接：15. 三数之和，难度：中等。

    给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

    示例 1:

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

    输出: [[-1,-1,2],[-1,0,1]]

    解释:

    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    注意，输出的顺序和三元组的顺序并不重要。

    示例 2:

    输入: nums = [0,1,1]

    输出: []

    解释: 唯一可能的三元组和不为 0 。

    示例 3:

    输入: nums = [0,0,0]

    输出: [[0,0,0]]

    解释: 唯一可能的三元组和为 0 。

    约束:

    • 3 <= nums.length <= 3000
    • -10^5 <= nums[i] <= 10^5
    提示 1

    So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!

    提示 2

    For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

    提示 3

    The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

    思路
    上一题下一题

    1. 三个数相加等于0，等同于两个数相加的和等于负的第三个数。
    2. 有两种方案可供选择：
      1. 先定下一个数，然后查找另外两个数。
      2. 先定下两个数，然后查找第三个数。
    3. 如果选择方案2，需要用到Map。因为需要对nums去重复；在Map中查找第三个数时，还需要避开已经定下的两个数，实现起来会比较麻烦。
    4. 如果选择方案1，查找另外两个数时，需要用到双指针算法。
    5. 对于方案2，仅给出了Python示例代码。下文重点讲方案1。

    步骤

    1. 对nums进行排序。
    2. 遍历nums。

    3. 伪代码：

      for (i = 0; i < nums.length; i++) {
   left = i + 1
   right = nums.length - 1

   while (left < right) {
      if (condition1) {
         left += 1
      } else (condition2) {
         right -= 1
      }
   }
}

    复杂度

    时间复杂度

    O(N * N)

    空间复杂度

    O(N)

    题解语言： Python Ruby Go C++ JavaScript C# Java

    Python # 

    # If you want the program to run faster, uncomment the two places in the code. 
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # nums_2 = []
        # for i, num in enumerate(nums):
        #     if i >= 3 and num == nums[i - 1] == nums[i - 2] == nums[i - 3]:
        #         continue
        #     nums_2.append(num)
        # nums = nums_2
        results = set()

        for i, num in enumerate(nums[:len(nums) - 2]):
            # if num > 0:
            #     break
            left = i + 1
            right = len(nums) - 1

            while left < right:
                sum_ = nums[left] + nums[right]
                if sum_ == -num:
                    results.add((num, nums[left], nums[right]))
                    left += 1
                elif sum_ > -num:
                    right -= 1
                else:
                    left += 1

        return list(results)

    Ruby # 

    # @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
  nums.sort!
  results = Set.new

  nums_2 = []
  nums.each_with_index do |num, i|
    next if i >= 3 && num == nums[i - 1] && num == nums[i - 2] && num == nums[i - 3]
    nums_2.append(num)
  end

  nums = nums_2

  # Iterate through each number as potential first element
  (0...nums.length - 2).each do |i|
    break if nums[i] > 0

    left = i + 1
    right = nums.length - 1

    # Two-pointer approach for remaining elements
    while left < right
      current_sum = nums[i] + nums[left] + nums[right]
      if current_sum == 0
        # Add sorted triplet to avoid duplicates
        results.add([nums[i], nums[left], nums[right]])
        left += 1
        right -= 1
      elsif current_sum < 0
        left += 1 # Need larger sum
      else
        right -= 1 # Need smaller sum
      end
    end
  end

  results.to_a
end

    Go # 

    func threeSum(nums []int) [][]int {
    sort.Ints(nums)

    nums2 := make([]int, 0)
    for i, num := range nums {
        if i >= 3 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] {
            continue
        }
        nums2 = append(nums2, num)
    }

    nums = nums2
    results := make([][]int, 0)
    seen := make(map[string]bool)

    for i := 0; i < len(nums)-2; i++ {
        // if nums[i] > 0 {
        //     break
        // }

        left := i + 1
        right := len(nums) - 1

        for left < right {
            sum := nums[left] + nums[right]
            if sum == -nums[i] {
                triplet := []int{nums[i], nums[left], nums[right]}
                key := fmt.Sprintf("%d,%d,%d", triplet[0], triplet[1], triplet[2])
                if !seen[key] {
                    results = append(results, triplet)
                    seen[key] = true
                }
                left++
            } else if sum > -nums[i] {
                right--
            } else {
                left++
            }
        }
    }

    return results
}

    C++ # 

    class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        // Uncomment to speed up
        // vector<int> nums2;
        // for (int i = 0; i < nums.size(); i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] &&
        //     nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.push_back(nums[i]);
        // }
        // nums = nums2;

        vector<vector<int>> results;
        set<vector<int>> seen;

        for (int i = 0; i < nums.size() - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == -nums[i]) {
                    vector<int> triplet = {nums[i], nums[left], nums[right]};

                    if (seen.find(triplet) == seen.end()) {
                        results.push_back(triplet);
                        seen.insert(triplet);
                    }

                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
};

    JavaScript # 

    /**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);

    // Uncomment to speed up
    // let nums2 = [];
    // for (let i = 0; i < nums.length; i++) {
    //     if (i >= 3 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3]) {
    //         continue;
    //     }
    //     nums2.push(nums[i]);
    // }
    // nums = nums2;

    const results = [];
    const seen = new Set();

    for (let i = 0; i < nums.length - 2; i++) {
        // Uncomment to speed up
        // if (nums[i] > 0) {
        //     break;
        // }
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[left] + nums[right];

            if (sum === -nums[i]) {
                const triplet = [nums[i], nums[left], nums[right]];
                const key = triplet.join(',');
                if (!seen.has(key)) {
                    results.push(triplet);
                    seen.add(key);
                }
                left++;
            } else if (sum > -nums[i]) {
                right--;
            } else {
                left++;
            }
        }
    }

    return results;
};

    C# # 

    public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);

        // Uncomment to speed up
        // var nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.Add(nums[i]);
        // }
        // nums = nums2.ToArray();

        var results = new List<IList<int>>();
        var seen = new HashSet<string>();

        for (int i = 0; i < nums.Length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.Length - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    var triplet = new List<int> { nums[i], nums[left], nums[right] };
                    string key = string.Join(",", triplet);
                    if (!seen.Contains(key)) {
                        results.Add(triplet);
                        seen.Add(key);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
}

    Java # 

    class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        // Uncomment to speed up
        // List<Integer> nums2 = new ArrayList<>();
        // for (int i = 0; i < nums.length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.add(nums[i]);
        // }
        // nums = nums2.stream().mapToInt(i -> i).toArray();

        List<List<Integer>> results = new ArrayList<>();
        var seen = new HashSet<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[left], nums[right]);
                    if (!seen.contains(triplet)) {
                        results.add(triplet);
                        seen.add(triplet);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
}
    题解语言： Python Ruby Go C++ JavaScript C# Java

    其它语言

    欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 15. 三数之和。

    题解2的思路：使用 Map（慢而复杂）

    请参考题解1的思路，本处仅给出代码，用来解释为什么使用 Map 不是一个好办法。

    复杂度

    时间复杂度

    O(N * N)

    空间复杂度

    O(N)

    Python # 

    # from collections import defaultdict

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = duplicate_removed_nums(nums)

        results = set()
        num_to_indices = defaultdict(list)

        for i, num in enumerate(nums):
            num_to_indices[num].append(i)

        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if -(nums[i] + nums[j]) in num_to_indices:
                    for index in num_to_indices[-(nums[i] + nums[j])]:
                        if index not in (i, j):
                            result = [nums[i], nums[j], nums[index]]
                            result.sort()
                            results.add(tuple(result))

        return list(results)


def duplicate_removed_nums(nums):
    num_to_count = defaultdict(int)

    for i, num in enumerate(nums):
        if num_to_count[num] <= 2 or (num_to_count[num] <= 3 and num == 0):
            num_to_count[num] += 1

    new_nums = []

    for num in num_to_count:
        new_nums.extend([num] * num_to_count[num])

    return new_nums

    其它语言

    欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 15. 三数之和。
    上一题下一题