1. 两数之和

难度：简单

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

使用一个HashMap，数组的值作为 key，数组的下标作为 value。

遍历数组，计算当前能得到目标和的补偿值compensation，去HashMap里面找compensation，找得到就返回，找不到就把当前的元素按上述规则放进HashMap。

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer,Integer> indexOfNums = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int compensation = target - nums[i];
        if (indexOfNums.containsKey(compensation)) {
            return new int[]{indexOfNums.get(compensation), i};
        }else {
            indexOfNums.put(nums[i], i);
        }
    }
    return null;
}

217. 存在重复元素

难度：简单

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

用HashSet实现，HashSet不包含重复的元素。

public boolean containsDuplicate (int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    return set.size() < nums.length;
}

594. 最长和谐子序列

难度：简单

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].

说明: 输入的数组长度最大不超过20,000.

先设置一个HashMap，存储数组中每个元素出现的频率。

找到值相差 1 的两个元素中，出现频率最高的。

public int findLHS(int[] nums) {
    Map<Integer, Integer> freqForNum = new HashMap<>();
    for (int num : nums) {
        freqForNum.put(num, freqForNum.getOrDefault(num, 0) + 1);
    }
    int longest = 0;
    for (Integer integer : freqForNum.keySet()) {
        if (freqForNum.containsKey(integer + 1)) {
            longest = Math.max(longest, freqForNum.get(integer) + freqForNum.get(integer + 1));
        }
    }
    return longest;
}

128. 最长连续序列

难度：困难

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

先用一个HashSet把数组元素都装起来，再遍历集合中的每个元素，如果集合中不含当前元素 - 1的元素，说明当前元素可以考虑作为一个连续子序列的开头，继续查看集合中是否有当前元素 + 1的元素，如果有的话，续上。最后返回最长连续序列的长度。

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    int longest = 0;

    for (Integer num : set) {
        if (!set.contains(num - 1)) {
            int curNum = num;
            int sequenceLength = 1;
            while (set.contains(curNum + 1)) {
                curNum += 1;
                sequenceLength += 1;
            }
            longest = Math.max(longest, sequenceLength);
        }
    }
    return longest;
}