欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#1 Tow Sum

程序员文章站 2024-02-29 10:42:16
...

My solution:

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

reference solution:

Approach 1: Brute force

time complexity: O(n2)                  

space complexity: O(1)

public 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[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

对比后需要改进的地方: 

1.  没有必要新声明一个result,直接返回更简洁

return new int[] {i, j};

2. 没有找到结果时,不应该返回默认result赋值,应该学会抛出异常

throw new IllegalArgumentException("No tow sum solution");

 

Approach 2:Two-pass Hash Table

What is the best way to maintain a mapping of each element in the array to its index? A hash table.

time complexity: O(n)                  

space complexity: O(n)

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

注意点:

1. map的声明

Map<Integer, Integer> map = new HashMap<>();

2. map的方法   (关于hashmap:https://www.cnblogs.com/skywang12345/p/3310835.html#b2

map.put(nums[i], i)
map.containsKey(complement)
map.get(complement)

 

Approach 3: One-pass Hash Table

While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table.

time complexity: O(n)                  

space complexity: O(n)

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");
}