两数之和

1. 两数之和

题目描述

解题思路

class Solution {
public int[] twoSum(int[] nums, int target) {
// 1.最朴素的思路：第一层for循环找第一个数，然后第二层for循环找第二个数
// 这种方法时间复杂度是O(n^2)
//return firstSolution(nums, target);
// 2. 先排序，然后使用双指针的方法从两头进行遍历
// 这种方法时间复杂度是O(nlogn)，但是有一个问题，现在需要返回的是下标，排序后下标信息会丢失
// 这里也可以考虑再使用一个哈希表来进行值到下标的映射，但是这样不如直接使用哈希表来解决这个问题
// 3. 使用哈希表，这样就只需要遍历一次数组即可完成查找
// 这种方法时间复杂度是O(n)
Map<Integer, Integer> hashmap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int ret = target - nums[i];
if (hashmap.containsKey(ret)) {
return new int[] {hashmap.get(ret), i};
}
hashmap.put(nums[i], i);
}
return new int[0];
}

    int[] firstSolution(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];
    }
}