1.Two-Sum.md

1. Two Sum

題目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than $O(N^2)$ time complexity?

思路

1. 暴力法，使用雙層for loop處理 $O(N^2)$
2. 利用Hash Map ，或類似特性處理 $O(N)$

Code

• $O(N^2)$

  • PHP

    class Solution {
    
        /**
         * O(N^2) solution
         * @param Integer[] $nums
         * @param Integer $target
         * @return Integer[]
         */
        function twoSum($nums, $target) {
            $size = count($nums);
            for ($i = 0; $i < $size-1; $i++) {
                for ($j = $i+1; $j < $size; $j++) {
                    if ($nums[$i]+$nums[$j] === $target) {
                        return [$i, $j];
                    }
                }
            }
        }
    }

  • Go

    • Runtime: 28 ms, faster than 33.79% of Go online submissions for Two Sum.
    • Memory Usage: 3.7 MB, less than 88.51% of Go online submissions for Two Sum.

    func twoSum(nums []int, target int) []int {
        for i, num := range nums {
            for j := i+1; j < len(nums); j++ {
                if (num + nums[j] == target) {
                    return []int{i, j}
                }
            }
        }
        
        return nil
    }

• $O(N)$

  • PHP

    class Solution {
    
        /**
         * O(N) solution
         * @param Integer[] $nums
         * @param Integer $target
         * @return Integer[]
         */
        function twoSum($nums, $target) {
            $size = count($nums);
            $nums_match = [];
            
            for ($i = 0; $i < $size; $i++) {
                
                $pair = $target - $nums[$i]; // 找出需要的值
                
                if (!isset($nums_match[$pair])) { // 若需要的值不再對照表中則新增
                    $nums_match[$pair] = $i;
                }
                
                if (isset($nums_match[$nums[$i]]) && $nums_match[$nums[$i]] != $i) { // 對照表中存在此值，且此值的index 必須和當前 index不同，避免當兩個值相同時判斷錯誤
                    return [$nums_match[$nums[$i]], $i];
                }
                
            }
            
            return [];
        }
    }

  • Go

    • Runtime: 4 ms, faster than 96.98% of Go online submissions for Two Sum.
    • Memory Usage: 4.3 MB, less than 28.43% of Go online submissions for Two Sum.

    func twoSum(nums []int, target int) []int {
        hashMap := make(map[int]int)
        
        for i, num := range nums {
            anotherIndex, isExist := hashMap[num]
            if (isExist && i != anotherIndex) {
                return []int{i, anotherIndex}
            }
            
            hashMap[target-num] = i
        }
        
        return nil;
    }