IOS algorithm solution problem
1. A brief introduction to summing three numbers
For an array of integers, does a, b, c exist such that a + b + c = 0, return a b c array, and only one is returned in the same array:
For example:
[-1, -2, 6, 5, 0, 1, 2, -1, -1] Return [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]]
Key points:
① Find three numbers with sum of 0
② Remove the same item, for example: The array above actually has three groups [-1, 0, 1], but we only need to add 1 group
Never use itfor loopagainSet a layer of for loopTo deal with this problem, some people think that two-layer for loop solution is OK. One layer looks for A, two layer looks for B, and determine whether the array exists.C = - (A + B), The idea is correct, but the time complexity is very highO(n^2) And when you get started, you will find that it is more complicated to deal with heavy-duping problems.
The method is:
Arraynums pre-order arrangement
Thenfor loop, set upMinimum value subscript low = i + 1, Maximum value subscript high = - 1
Maximum value, minimum value Continuously shrink and search, repeated removal and always maintainlow < high (Because it is arranged in a positive order, large value >= small value)
such that 0 - nums[i] = nums[low] + nums[high] (i.e.: 0 = nums[low] + nums[high] + nums[i])
Create a new array Add [nums[low], nums[high], nums[i]] that meet the conditions, and return after the loop ends.
Next we look at the code
2. Code
let num:[Int] = [0, 0, 0, 0, -1, 0, 1, 9, 7, 4]
print("Return result: \((nums: num))")
func caculate(nums: [Int]) -> [[Int]] {
//Array element is less than 2 and returns directly if < 2 {
return []
}
//Create an empty array to add [A,B,C] var result:[[Int]] = []
//Sorting the original array array in a positive order, this step is very important, and out-of-order arrays are difficult to deal with let sort:[Int] = ()
//Loop positive order array for i in 0..<-1 {
//Create the minimum value subscript, the maximum value subscript var low:Int = i+1
var high:Int = - 1
//A+B+C=0 Define -C for later let A+B=-C
let target:Int = 0 - sort[i]
// If the two numbers are equal, skip the next loop if i>0 && sort[i] == sort[i-1] {
continue
}
//Always guarantee maximum value subscript > minimum value subscript //The idea is that the maximum value will not decrease, the minimum value will continue to increase, and the minimum value will not exceed the maximum value //Until the corresponding value is found, the same value is deduplicated
while low < high {
//Create sum as: two numbers and A+B let sum:Int = sort[low] + sort[high]
//If A+B == -C means A+B+C == 0 if sum == target {
//Add new elements in the array ([sort[low], sort[high], sort[i]])
//If the current minimum value is equal to the next bit, shift the subscript forward and de-reduce it while low < high && sort[low] == sort[low + 1] {
low += 1
}
//If the current maximum value is equal to the previous digit, shift the index forward and de-reduce it while low < high && sort[high] == sort[high - 1] {
high -= 1
}
//The minimum value moves one bit backward, and the maximum value moves one bit forward. Continue to shrink until it jumps out of while low += 1
high -= 1
}else if sum < target{
//If A+B == -C means A+B+C == 0 low += 1
}else {
//If A+B == -C means A+B+C == 0 high -= 1
}
}
}
return result
}
Return result:[[0, 1, -1], [0, 0, 0]]
This is the article about solving the problem of sum of three numbers in IOS algorithm. For more related contents to solve the sum of three numbers in IOS algorithm, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!