迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given an array Note: The solution set must not contain duplicate quadruplets. Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 给定一个包含 n 个整数的数组 注意: 答案中不可以包含重复的四元组。 示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 40ms 1 class Solution { 2 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { 3 let sortedNums = nums.sorted() 4 var results = [[Int]]() 5 findNSum(sortedNums, left: 0, right: sortedNums.count - 1, target:target, N: 4, result: [Int](), results: &results) 6 return results 7 } 8 9 func findNSum(_ sortedNums: [Int], left: Int, right: Int, target: Int, N: Int, result: [Int], results: inout [[Int]]) { 10 if (right - left + 1) < N || N < 2 || target < N * sortedNums[left] || target > sortedNums[right] * N { 11 return 12 } 13 14 if N > 2 { 15 for i in left...right { 16 if i == left || sortedNums[i] != sortedNums[i-1] { 17 var result = result 18 result.append(sortedNums[i]) 19 findNSum(sortedNums, left: i+1, right: right, target: target-sortedNums[i], N: N-1, result: result, results: &results) 20 } 21 } 22 } else { 23 var left = left 24 var right = right 25 while left < right { 26 let sum = sortedNums[left] + sortedNums[right] 27 if sum == target { 28 results.append(result + [sortedNums[left], sortedNums[right]]) 29 left = left + 1 30 while left < right && sortedNums[left] == sortedNums[left - 1] { 31 left = left + 1 32 } 33 } else if sum > target { 34 right = right - 1 35 } else { 36 left = left + 1 37 } 38 } 39 } 40 } 41 } 60ms 1 class Solution { 2 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { 3 if nums.count < 4 {return []} 4 let sorted = nums.sorted() 5 var quardruplets = [[Int]]() 6 for i in 0..<(nums.count - 3) { 7 if i > 0 && sorted[i] == sorted[i - 1] {continue} 8 for j in (i + 1)..<(nums.count - 2) { 9 if j > i + 1 && sorted[j] == sorted[j - 1] {continue} 10 var k = j + 1 11 var l = nums.count - 1 12 let twoSumTarget = target - sorted[i] - sorted[j] 13 while k < l { 14 let twoSum = sorted[k] + sorted[l] 15 if twoSum < twoSumTarget {k += 1} 16 if twoSum > twoSumTarget {l -= 1} 17 if twoSum == twoSumTarget { 18 quardruplets.append([sorted[i], sorted[j], sorted[k], sorted[l]]) 19 repeat {k += 1} while k < l && sorted[k] == sorted[k - 1] 20 repeat {l -= 1} while k < l && sorted[l] == sorted[l + 1] 21 } 22 } 23 } 24 } 25 return quardruplets 26 } 27 } 72ms 1 class Solution { 2 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { 3 let count = nums.count 4 guard count >= 4 else { return [] } 5 let nums = nums.sorted() 6 7 var result = [[Int]]() 8 for i in 0..<count - 3 { 9 if i > 0 && nums[i] == nums[i - 1] { 10 continue 11 } 12 var threeSum = target - nums[i] 13 14 for j in i + 1..<count - 2 { 15 if j > i + 1 && nums[j] == nums[j - 1] { 16 continue 17 } 18 var twoSum = threeSum - nums[j] 19 var left = j + 1, right = count - 1 20 while left < right { 21 if nums[left] + nums[right] == twoSum { 22 result.append([nums[i], nums[j], nums[left], nums[right]]) 23 while left < right && nums[left] == nums[left + 1] { 24 left += 1 25 } 26 while left < right && nums[right] == nums[right - 1] { 27 right -= 1 28 } 29 left += 1 30 right -= 1 31 } else if nums[left] + nums[right] < twoSum { 32 left += 1 33 } else { 34 right -= 1 35 } 36 } 37 } 38 } 39 return result 40 } 41 } 88ms 1 class Solution { 2 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { 3 var res: [[Int]] = [[Int]]() 4 let len = nums.count 5 if len < 4 {return res} 6 var nums = nums.sorted(by: <) 7 for i in 0..<len 8 { 9 if i > 0 && nums[i] == nums[i - 1] 10 { 11 continue 12 } 13 for j in (i + 1)..<len 14 { 15 //第二个数的去重处理 16 if j > i + 1 && nums[j] == nums[j - 1] 17 { 18 continue 19 } 20 var l:Int = j + 1 21 var r = len - 1 22 while (l < r) 23 { 24 var sum = nums[i] + nums[j] + nums[l] + nums[r] 25 if sum == target 26 { 27 res.append([nums[i], nums[j], nums[l], nums[r]]) 28 while (l < r && nums[l] == nums[l + 1]) { l += 1} 29 while (l < r && nums[r] == nums[r - 1]) { r -= 1} 30 l += 1 31 r -= 1 32 } 33 else if sum < target {l += 1} 34 else {r -= 1} 35 } 36 } 37 } 38 return res 39 } 40 } 108ms 1 class Solution { 2 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { 3 4 var array = nums.sorted() 5 var result = [[Int]]() 6 guard nums.count >= 4 else { return result } 7 8 for i in 0 ..< nums.count - 3 { 9 for j in i + 1 ..< nums.count - 2 { 10 var left = j + 1 11 var right = nums.count - 1 12 while left < right { 13 let sum = array[i] + array[j] + array[left] + array[right] 14 if sum == target { 15 let temp = [array[i], array[j], array[left], array[right]] 16 if !result.contains(temp) { 17 result.append(temp) 18 } 19 left += 1 20 right -= 1 21 } else if sum > target { 22 right -= 1 23 } else { 24 left += 1 25 } 26 } 27 } 28 } 29 return result 30 } 31 } 668ms 1 class Solution { 2 func twoSum(sortedNums: [Int], firstNumIndex: Int, secondNumIndex: Int, target: Int) -> [[Int]] { 3 var low = secondNumIndex + 1 4 var high = sortedNums.count - 1 5 var result = [[Int]]() 6 let firstNum = sortedNums[firstNumIndex] 7 let secondNum = sortedNums[secondNumIndex] 8 9 // 将 low 往右移,并跳过重复 10 func moveLow() { 11 repeat { 12 low += 1 13 } while sortedNums[low] == sortedNums[low - 1] && low < high 14 } 15 16 // 将 high 往左移,并跳过重复 17 func moveHigh() { 18 repeat { 19 high -= 1 20 } while sortedNums[high] == sortedNums[high + 1] && low < high 21 } 22 23 while low < high { 24 let sum = sortedNums[low] + sortedNums[high] + firstNum + secondNum 25 26 if sum < target { 27 moveLow() 28 } else if sum > target { 29 moveHigh() 30 } else { // sum == target 31 result.append([firstNum, secondNum, sortedNums[low], sortedNums[high]]) 32 33 moveLow() 34 moveHigh() 35 } 36 } 37 38 return result 39 } 40 41 func threeSum(sortedNums: [Int], firstNumIndex: Int, target: Int) -> [[Int]] { 42 var secondNumIndex = firstNumIndex + 1 43 var result = [[Int]]() 44 45 while secondNumIndex < sortedNums.count - 2 { 46 result.append(contentsOf: twoSum( 47 sortedNums: sortedNums, 48 firstNumIndex: firstNumIndex, 49 secondNumIndex: secondNumIndex, 50 target: target 51 )) 52 53 repeat { 54 secondNumIndex += 1 55 } while sortedNums[secondNumIndex] == sortedNums[secondNumIndex - 1] && 56 secondNumIndex < sortedNums.count - 2 57 } 58 59 return result 60 } 61 62 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] { 63 guard nums.count >= 4 else { return [] } 64 var result = [[Int]]() 65 var firstNumIndex = 0 66 let sortedNums = nums.sorted() 67 68 while firstNumIndex < sortedNums.count - 3 { 69 result.append(contentsOf: threeSum( 70 sortedNums: sortedNums, 71 firstNumIndex: firstNumIndex, 72 target: target 73 )) 74 75 repeat { 76 firstNumIndex += 1 77 } while sortedNums[firstNumIndex] == sortedNums[firstNumIndex - 1] && 78 firstNumIndex < sortedNums.count - 3 79 } 80 81 return result 82 } 83 }
|
请发表评论