[Swift] 3Sum

January 01, 2017 0 Comments

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)


解法: 
https://www.youtube.com/watch?v=-AMHUdZc9ss
利用前後兩個指標和最左邊開始的數相加去比對。



func threeSum(_ nums: [Int]) -> [[Int]] {
    var returnArray = [[Int]]() //Array for saved and return
    
    if (nums.count < 3) {return returnArray}
    
    let orgArray = nums.sorted() //sort array first
    
    
    for i in 0...orgArray.count - 3 {
        if i == 0 || orgArray[i] > orgArray[i - 1] {
           //左右兩邊的pointer
           var start = i + 1
           var end = orgArray.count - 1
            
            while ( start < end ) {
                //如果相加等於0 就存入要回傳的陣列中
                if (orgArray[i] + orgArray[start] + orgArray[end] == 0) {
                    let newap = [orgArray[i] , orgArray[start] , orgArray[end]]
                    returnArray.append(newap)
                }
                //如果三個加起來比0還小 , 則移動start 這個pointer
                if (orgArray[i] + orgArray[start] + orgArray[end] < 0) {
                    let currentStart = start
                    //如果pointer[A] 和 pointer[A+1] 相同的話就直接跳下一個
                    while (orgArray[start] == orgArray[currentStart] && start < end) {
                        start += 1
                    }
                }else{
                    let currentEnd = end
                    while (orgArray[end] == orgArray[currentEnd] && start < end) {
                        end -= 1
                    }
                }
            }
        }
    }
    return returnArray

}


0 comments:

Subscribe to: Post Comments (Atom)