LeetCode 1. Two Sum (Java)

tags: leetcode Java

Description

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.

給一個整數數組，找到兩個數使得他們的和等於一個給定的數 target。 你需要實現的函數twoSum需要返回這兩個數的下標, 並且第一個下標小於第二個下標。注意這裡下標的範圍是 0 到 n-1

Example

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

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

Idea

• Approach 1 (暴力法)
  • 利用雙迴圈找出哪兩個數字可以符合target，時間複雜度偏高
    $O(n^2)$
• Approach 2 (HashMap)
  • 遍歷整個陣列，將target和當前數字相減並存在HashMap裏並在接下來的迴圈當中檢查當前數字在HashMap中是否有相同數字
  • 例：map.get(nums[i])!=null代表HashMap中有我要的數字
  • 整體時間複雜度降到
    $O(n)$

Code

Approach 1

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0;i < nums.length;i++){
            for(int j = i+1; j < nums.length;j++){
                if(nums[i] == target - nums[j]){
                    return new int[] {i,j};
                }
                    
            }
        }
        throw new IllegalArgumentException("error");
    }
}

Approach 2

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int len = nums.length;
        int[] result = new int[2];
        for (int i = 0;i < len;i++){
            if(map.get(nums[i]) != null){//檢查HashMap中是否有此數
                return new int[] {map.get(nums[i]), i};
            }
            map.put(target - nums[i],i);//將理想配對數字放到HashMap中
        }
        return result;
    }
}

方法二相較於方法一暴力解法整整快出了50倍

Result

Approach 1

Runtime: 48 ms, faster than 28.98% of Java online submissions for Two Sum. Memory Usage: 39.4 MB, less than 37.92% of Java online submissions for Two Sum.

Approach 2

Runtime: 1 ms, faster than 99.59% of Java online submissions for Two Sum. Memory Usage: 39.2 MB, less than 50.00% of Java online submissions for Two Sum.