1.两数之和
可以先对数组进行排序，然后使用双指针方法或者二分查找方法。这样做的时间复杂度为 O(NlogN)，空间复杂度为 O(1)。
用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]，如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> indexForNum = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (indexForNum.containsKey(target - nums[i])) {
return new int[]{indexForNum.get(target - nums[i]), i};
} else {
indexForNum.put(nums[i], i);
}
}
return null;
}
}217.存在重复元素
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
return set.size() < nums.length;
}
}594.最长和谐子序列
和谐序列中最大数和最小数之差正好为 1，应该注意的是序列的元素不一定是数组的连续元素。
class Solution {
public int findLHS(int[] nums) {
Map<Integer, Integer> countForNum = new HashMap<>();
for (int num : nums) {
countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
}
int longest = 0;
for (int num : countForNum.keySet()) {
if (countForNum.containsKey(num + 1)) {
longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
}
}
return longest;
}
}128.最长连续序列
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num-1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum+1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}