Leetcode 1. Two Sum

算法 Java Leetcode Golang

Return indices of the two numbers.

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
See it on Leetcode

For example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
It should return [0, 1].

Hint

You may assume that each input would have exactly one solution.

Solution #1 Brute Force - 38ms / 59ms

• java
• go

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; 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, 0}; 
    }
}

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

Solution #2 One-pass Hash Table - 7ms / 9ms

• java
• go

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution"); 
    }
}

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i := range nums {
        complement := target - nums[i]
        elem, ok := m[complement]
        if ok {
            return []int{elem, i}
        }
        m[nums[i]] = i
    }
    return []int{0, 0}
}