LeetCode 1. Two sum

Two sum是LeetCode easy經典題（因為是problem 1），但不幸地我是看過「How to: Work at Google - Example Coding/Engineering interview」才來解這題，所以已經知道怎麼解了。

題目

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]
Explanation: 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]

先想到的解法

直覺就是從第一個元素值與後面的元素值一個個相加看是否與target相同，所以需要一個迴圈遍歷陣列，裏面另一個迴圈遍歷後面的元素並相加測試是否和target相等。因為外內兩個回圈所以時間複雜度為O(n^2)，空間複雜度O(1)。

nums=[1,2,3], target=4
========================outter:L1, inner:L1=========================
        v (i=0)
  nums=[1,2,3]
          ^ (j=i+1)
  sum=3 != target 

========================outter:L1, inner:L2=========================
        v (i=0)
  nums=[1,2,3]
            ^ (j=i+2)
  sum=4 == target

Main.java

package com.abc.demo;


import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(twoSum(new int[]{1, 2, 3}, 4))); // [0, 2]
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 5}, 9))); // [0, 1]
    }

    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) { // 遍歷陣列的每個元素
            int j = i + 1; // 外迴圈元素的下個元素的索引
            while (j < nums.length) { // 遍歷外迴圈目前元素後的每個元素
                if (nums[i] + nums[j] == target) { 外迴圈目前元素值與後面每個元素相加看是否符合target
                    return new int[]{i, j}; // 回傳符合的兩個元素的索引陣列
                }
                j++; // 遞增外迴圈元素的下個元素的索引
            }
        }
        return new int[0];
    }

}

裡面的迴圈也可用for迴圈。但覺得用while迴圈似乎比較容易思考，彈性較大。

Main.java

package com.abc.demo;


import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(twoSum(new int[]{1, 2, 3}, 4))); // [0, 2]
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 5}, 9))); // [0, 1]
    }

    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

}

更加解

用一個Map容器來記錄遍歷過的元素值，然後檢視目前元素值的補數（與target的差）是否存在容器中。題目特別提到只有一個結果，所以可以以值作為Map的key來儲存索引位置（因為結果要回傳相加等於target的兩個元素的索引）。一個廽圈時間複雜度O(n)，需要一個容器紀錄遍歷過的元素所以空間複雜度為O(n)。

nums=[1,2,3], target=4
L1:=================================================================
  compl={}
        v (i=0)
  nums=[1,2,3]  

  compl={3=1}

L2:=================================================================
  compl={3=1}
          v (i=1)
  nums=[1,2,3]
  
  compl={3=1, 2=2}

L3:=================================================================
  compl={3=1, 2=2}
            v (i=2)
  nums=[1,2,3]

  complement 1 of 3 found in compl

Main.java

package com.abc.demo;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(twoSum(new int[]{1, 2, 3}, 4)));
        System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 5}, 9)));
    }

    public static int[] twoSum(int[] nums, int target) {
        Map>Integer, Integer< compl = new HashMap<>(); // key:element, value:index
        for (int i = 0; i < nums.length; i++) { // tc:O(n)
            if (compl.containsKey(target - nums[i])) { // check if map has complement value of current element's value
                return new int[]{i, compl.get(target - nums[i])};
            }
            compl.put(nums[i], i); // no match, put current value into complements map
        }
        return new int[0];
    }
}

題目變化

若不限定只有一個結果的情況？