1. Two Sum

liqimore

2021 年 08 月 27 日

0 次浏览

暂无评论

2457字数

刷题

Problem

https://leetcode-cn.com/problems/two-sum/

Solutions

Enumerate

Go through nums[] array and set i = len, j = i + 1. Then loop every possible cases by using 2 for loop.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {

            for (int j = i + 1; j < n ; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
      
        return new int[]{};

    }
}

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

Time complexity: O(N^2). N is the length of num array. If possible, loop every elements in the arrray.

Space Complexity: O(1).

Hashtable

In order to get indices i and j, we need target = nums[i] + nums[j], which is the same as target - nums[i] = nums[j].

So, if current nums[i] matches to target - nums[i], we find the indexes (hashtale(target-nums[i]), i). It basicly using
a hashtable to represent the other value(i or j) from the enumerate version.

class Solution {
    public int[] twoSum(int[] nums, int target) {

        // key = elements in nums, value = index
        Map<Integer, Integer> hashMap = new HashMap<>(nums.length);

        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(target - nums[i])) {
                return new int[]{hashMap.get(target - nums[i]), i};
            }
            hashMap.put(nums[i], i);
        }
        return new int[]{};

    }
}

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

    hashmap := make(map[int]int)

    for i := 0; i < len(nums); i++ {
        if v, ok := hashmap[target - nums[i]]; ok {
            return []int{v, i}
        }
        hashmap[nums[i]] = i
    }
    return nil
}

Time complexity: O(N). N is the length of num array. If possible, loop every elements in the arrray ONCE.

Space Complexity: O(N), we saved elements dynamically in a hashtable.