Leetcode.com/problems/3s…

Discuss:www.cnblogs.com/grandyang/p…

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i ! = j, i ! = k, and j ! = k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [1, 2, 1, 4] Output: [[1, 1, 2], [1, 1]]Copy the code

Example 2:

Input: nums = []
Output: []
Copy the code

Example 3:

Input: nums = [0]
Output: []
Copy the code

Constraints:

  • 0 <= nums.length <= 3000

  • -105 <= nums[i] <= 105

Solution a:

Brute force will run out of time.

class Solution { fun threeSum(nums: IntArray): List<List<Int>> { if (nums.size < 3) { return mutableListOf() } val result = mutableListOf<List<Int>>() var isOnceAllZero = false for (i in 0.. nums.size - 3) { val x = nums[i] for (j in i + 1.. nums.size - 2) { val y = nums[j] for (k in j + 1 until nums.size) { val z = nums[k] if (x + y + z == 0) { val item = mutableListOf<Int>() item.add(x) item.add(y) item.add(z) var isAdd = true if (x == y && y == z && ! isOnceAllZero) { isOnceAllZero = true result.add(item) continue } if (result.isNotEmpty()) { kotlin.run breaking@{ result.forEach { if (it.containsAll(item)) { isAdd = false return@breaking } } } } if (isAdd) { result.add(item) } } } }  } return result } }Copy the code

Method 2:

Using Map to store values of subscripts and arrays eliminates a layer of loops, but this still times out.

class Solution { fun threeSum(nums: IntArray): List<List<Int>> { if (nums.size < 3) { return mutableListOf() } val result = mutableListOf<List<Int>>() val map = mutableMapOf<Int,Int>() var isOnceAllZero = false for (index in nums.indices){ map[index] = nums[index] } for (i in 0.. nums.size - 3) { val x = nums[i] for (j in i + 1.. nums.size - 2) { val y = nums[j] val z = Math.negateExact((x+y)) if (map.containsValue(z)&& map.values.lastIndexOf(z)>j){ val item = mutableListOf<Int>() item.add(x) item.add(y) item.add(z) var isAdd = true if (x  == y && y == z && ! isOnceAllZero) { isOnceAllZero = true result.add(item) continue } if (result.isNotEmpty()) { kotlin.run breaking@{ result.forEach { if (it.containsAll(item)) { isAdd = false return@breaking } } } } if (isAdd) { result.add(item) } } } }  return result } }Copy the code

Method 3:

Sort the original array, and then start iterating through the sorted array, not to the last one, but to the third from the bottom. We can do a prune optimization here, which is break when we get to a positive number, because the array is now ordered, and if the first number we fix is positive, then all the numbers that follow are positive, and we never have a sum of zero. If the number is equal to the previous number, skip it, because you don’t want to fix the same number twice. For the number iterated, subtract the fix from 0 to get a target, and then just find two numbers that add up to target. Use two Pointers to the first and last two numbers in the array starting after the fix number. If the sum of the two numbers happens to be target, store them in the result along with the fix number. The next step is to skip the duplicate digits, and both Pointers need to detect the duplicate digits. If the sum of the two numbers is less than target, the left pointer I is moved one bit to the right, making the number pointing to larger. Similarly, if the sum of two numbers is greater than target, the pointer j on the right is moved one bit to the left, making the number to point to smaller.

class Solution { fun threeSum(nums: IntArray): List<List<Int>> { if (nums.size < 3) { return mutableListOf() } val result = mutableListOf<List<Int>>() nums.sort() if (nums.first() > 0 || nums.last() < 0) { return mutableListOf() } for (k in 0.. nums.size - 3) { if (nums[k] > 0) { break } if (k > 0 && nums[k] == nums[k - 1]) { continue } val target = 0 - nums[k] var i = k + 1 var j = nums.size - 1 while (i < j) { when { nums[i] + nums[j] == target -> { val item = mutableListOf<Int>() item.add(nums[k]) item.add(nums[i]) item.add(nums[j]) result.add(item) while (i < j && nums[i] == nums[i + 1]) { ++i } while (i < j && nums[j] == nums[j - 1]) { --j } ++i --j } nums[i] + nums[j] < target -> { ++i } else -> { --j } } } } return result } }Copy the code

Method 4:

You can also take advantage of the fact that a Set cannot contain duplicates to prevent duplicates, so you don’t need to check if the number is fixed twice.

class Solution { fun threeSum(nums: IntArray): List<List<Int>> { if (nums.size < 3) { return mutableListOf() } val result = mutableSetOf<List<Int>>() nums.sort() if (nums.first() > 0 || nums.last() < 0) { return mutableListOf() } for (k in 0.. nums.size - 3) { if (nums[k] > 0) { break } val target = 0 - nums[k] var i = k + 1 var j = nums.size - 1 while (i < j) {  when { nums[i] + nums[j] == target -> { val item = mutableListOf<Int>() item.add(nums[k]) item.add(nums[i]) item.add(nums[j]) result.add(item) while (i < j && nums[i] == nums[i + 1]) { ++i } while (i < j && nums[j] == nums[j - 1]) { --j } ++i --j } nums[i] + nums[j] < target -> { ++i } else -> { --j } } } } return result.toList() } }Copy the code