How to solve the problem of Sum of three numbers in leetcode

Xiaobian to share with you how to solve the problem of the sum of three in leetcode, I believe most people still do not understand, so share this article for your reference, I hope you have a lot of harvest after reading this article, let's go to understand it together!

Title Link

https://leetcode-cn.com/problems/3sum/

Title Description

Given an array nums of n integers, determine whether there are three elements a, b, c in nums such that a + b + c = 0? Find all triples that satisfy the condition and are not duplicated.

Note: The answer must not contain duplicate triples.

For example, given the array nums = [-1, 0, 1, 2, -1, -4],

The set of triples that satisfy the requirement is:

[

[-1, 0, 1],

[-1, -1, 2]

]

solution train of thought

Tag: array traversal

First sort the array, fix a number nums[i] after sorting, then use the left and right pointers to point to the two ends behind nums[i], the numbers are nums[L] and nums[R] respectively, calculate the sum of three numbers to determine whether it satisfies 0, and then add it to the result set.

If nums[i] is greater than 0, then the sum of the three numbers must not equal 0, ending the loop.

If nums[i] == nums[i-1], it means that the number is repeated, which will lead to repeated results, so it should be skipped.

When sum == 0, nums[L] == nums[L+1] causes duplicate results and should be skipped, L++

When sum == 0, nums[R] == nums[R-1] causes duplicate results and should be skipped, R--

Time complexity: O(n^2), n is the array length

code

Java version

class Solution {

public static List threeSum(int[] nums) {

List ans = new ArrayList();

Array.sort(nums); //sort

int len = nums.length;

if(nums == null || len

< 3) return ans; for (int i = 0; i < len ; i++) { if(nums[i] >

0)break; //If the current number is greater than 0, then the sum of the three numbers must be greater than 0, so the loop ends

if(i > 0 && nums[i] == nums[i-1]) continue; //remove duplicate

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 a - b); // 排序 const len = nums.length; if(nums == null || len < 3) return ans; for (let i = 0; i < len ; i++) { if(nums[i] >

0)break; //If the current number is greater than 0, then the sum of the three numbers must be greater than 0, so the loop ends

if(i > 0 && nums[i] == nums[i-1]) continue; //remove duplicate

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