[Go] Array and string - Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

My code

func twoSum(numbers []int, target int) []int {
	length := len(numbers)
	lp, rp := 0, length-1

	for lp < rp {
		if numbers[lp]+numbers[rp] == target {
			break
		}
		if numbers[lp]+numbers[rp] > target {
			rp--
		}
		if numbers[lp]+numbers[rp] < target {
			lp++
		}
	}
	return []int{lp + 1, rp + 1}
}

• https://go.dev/play/p/6Sa87aaGgsK
• I tried to make simple code.
• This code uses lp and rp.
• when lp is same with rp then for loop will be end.
• first if condition will check numbers[lp] + numbers[rp] is same with target.
• if so, for loop will be breaken.
• if sum is greater than target then rp will be decrease.
• else situation, lp will decrease.

sample 0 ms submission

func twoSum(numbers []int, target int) []int {
    p1, p2 := 0, len(numbers)-1
    for p1 < p2 {
        sum := numbers[p1] + numbers[p2] 
        if sum > target {
            p2--
        } else if sum == target {
            return []int{ p1 + 1, p2 + 1 }
        } else {
            p1++
        }
    }
    return nil 
}

• This code is almost same with my code.

sample 3 ms submission

func twoSum(numbers []int, target int) []int {
    posByNum := make(map[int]int, len(numbers)/2)
    for i, num := range numbers {
        if pos, ok := posByNum[target-num]; ok {
            return []int{pos+1,i+1}
        }
        
        if num <= target/2 {
            posByNum[num] = i
        }
    }
    
    return []int{0, 1}
}

• This code uses map with half length of numbers.
• But initialization of size is not matter.
• for loop will run until end.
• first if condition will find the number which target minus num.
• maximum of minimum value is less than target/2.
  ex) 100 = (49,51)
• if num is less than target / 2, it will be added in order.

sample 4 ms submission

func twoSum(nums []int, target int) []int {
	var answer []int

	if len(nums) < 2 {
		return answer
	}

	left := 0
	right := len(nums) - 1

	for left < right {
		sum := nums[left] + nums[right]

		if sum == target {
			answer = append(answer, left + 1)
			answer = append(answer, right + 1)
			return answer
		} else if sum > target {
			right--
		} else {
			left++
		}
	}

	return answer
}

sample 5 ms submission

func twoSum(numbers []int, target int) []int {
    for i, j := 0, len(numbers) - 1; i < j; {
        if numbers[i] + numbers[j] == target {
            return []int{i + 1, j + 1}
        } else if numbers[i] + numbers[j] > target {
            j--
        } else {
            i++
        }
    }
    
    return []int{}
}

sample 6 ms submission & sample 5500 KB submission

func twoSum(numbers []int, target int) []int {
    left := 0
    right := len(numbers) - 1
    
    for {
        sum := numbers[left] + numbers[right]
        
        if sum > target {
            right -= 1
        } else if sum < target {
            left += 1
        } else {
            return []int{left+1, right+1}
        }
        
    }
}

sample 7 ms submission

func twoSum(numbers []int, target int) []int {
    hashMap := make(map[int]int)
	for currentIndex, value := range numbers {
		requiredIndex, isPresent := hashMap[target-value]
		if isPresent {
			return []int{requiredIndex+1, currentIndex+1}
		}
		hashMap[value] = currentIndex
	}
	return []int{}
}

sample 8 ms submission

func twoSum(numbers []int, target int) []int {
  i := 0
  j := len(numbers) - 1
  
  for i < j {
    sum := numbers[i] + numbers[j]

    if (sum == target) {
      break
    } else if sum > target {
      j--
    } else {
      i++
    }
  }
  
  return []int{i+1, j+1}
}

sample 5300 KB submission

func twoSum(numbers []int, target int) []int {
    f,l:=0,len(numbers)-1
    for f<l{
        sum:=numbers[f]+numbers[l]
        if sum<target{
            f++
        }else if sum>target{
            l--
        }else{
            return []int{f+1,l+1}
        }
    }
    return []int{}
}

sample 5400 KB submission

func twoSum(numbers []int, target int) []int {
    var output []int
    for i, _ := range(numbers) {
		for j, _ := range(numbers) {
			if i == j {
				continue
			}
			res := numbers[i] + numbers[j]
			if res == target {
				output = append(output, i+1, j+1)
				return output
			}
		}
	}
    return output
}