leetcode-1刷题

• • 暴力法
  • 哈希表

首先来看题目： 原题链接

暴力法是较为直观，容易想到的方法。通过遍历数组中每一个位置的元素，再遍历其他位置元素，判断加和是否为目标值。在第二次遍历中，可以只遍历当前元素后的元素，避免重复运算。两层遍历，时间复杂度为O(n²),没有额外的空间消耗，空间复杂度为O(1)。

class Solution {
    public int[] twoSum(int[] nums, int target) {
		int[] res = new int[2];
        boolean hasFound = false;
        for (int i = 0; !hasFound && i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = nums[i];
                    res[1] = nums[j];
                    hasFound = true;
                    break;
                }
            }
        }
        return res;
    }
}

通过暴力法发现，解决的关键在于查找算法：对于一个值为val的元素，需要在数组中查找是否存在值为(target - val)的元素。此时，可以想到，通过创建一个哈希表，遍历数组中的元素，如果哈希表中存在对应的值，则可以得到答案，如不存在，则将该元素存至哈希表中。通过这样的优化，只需要一趟遍历，时间复杂度降为O(n)，但是由于引进了一个哈希表，空间复杂度变为O(n)。

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    // 设定合理的初始容量，避免过小HashSet自动扩容影响效率，过大浪费内存
    HashSet set = new HashSet<>((int) (nums.length / 0.75f) + 1);
    for (int num : res) {
        if (set.contains(target - num)) {
            res[0] = target - num;
            res[1] = num;
            break;
        } else {
            set.add(num);
        }
    }
    return res;
}