ac solution code


  • 0

    The basic idea is to use two pointers: in each step of while loop, decide the next direction with the below IF statements:
    If nums[start] + nums[end] == target, return [start, end]
    If nums[start] + nums[end] < target, start++ to advance start boundary
    If nums[start] + nums[end] > target, end-- to rewind end boundary

    The spirit of TWO POINTERS is to use start..end window to approach target progressively to get linear time complexity.

        /*
         Solution1. Two Pointers - time = O(n); space = O(1)
         */
        func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
            var start = 0
            var end = nums.count - 1
            while (start <= end) {
                let sum = nums[start] + nums[end]
                if (sum == target) {
                    break;
                } else if (sum  < target) {
                    start += 1
                } else {
                    end -= 1
                }
            }
            // NOTE: nums index starts from 1, so add 1 to index accordingly
            return start < end ? [start + 1, end + 1] : [-1, -1]
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.