1.两数之和 （easy） 2021-01-16
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
这，力扣第一题，暴力解法。时间复杂度为O(nlogn),空间复杂度为O(1)。
如果使用哈希表来储存，先将数组存放进哈希表，然后遍历数组，每访问一个元素，就去哈希表中搜索target - nums[i]。
再优化算法就是，在遍历数组的时候，先搜索，在存放进哈希表 ，这么做，时间复杂度为O(n)，空间复杂度为O(n)。
class Solution { public int[] twoSum(int[] nums, int target) { for(int i = 0; i < nums.length ; i++){ for(int j = i + 1; j < nums.length; j++){ int sum = nums[i] + nums[j]; if(sum == target){ return new int[]{i, j}; } } } return null; } }
下面是使用栈的做法。
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ if(map.containsKey(target - nums[i])){ return new int[]{i, map.get(target - nums[i])}; }else{ map.put(nums[i], i); } } return null; } }
217.存在重复元素 （easy）2021-01-17
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回
true。如果数组中每个元素都不相同，则返回false。
使用Set的特性，无序不可重复。添加的时候如果重复添加失败会返回false。
class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for(int i = 0; i < nums.length; i++){ if(!set.add(nums[i])){ return true; } } return false; } }
594.最长和谐子序列 （easy） 2021-01-17
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
下面的代码是使用快慢指针的做法，先给数组排序，然后设置一个快指针一个慢指针，保持在值的差距小于1的距离。
class Solution { public int findLHS(int[] nums) { Arrays.sort(nums); int begin = 0, res = 0; for(int end = 0; end < nums.length; end++){ while(nums[end] - nums[begin] > 1){ begin++; } if(nums[end] - nums[begin] == 1){ res = Math.max(res, end - begin + 1); } } return res; } }
下面的代码是使用哈希表的做法。先将数据和存现的频次存放进哈希表，getOrDefault( , )函数图其字面意思，如果存在key = num值就取出其对应的value,不存在就返回一个默认值。然后遍历哈希表。
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.最长连续序列 （hard） 2021-01-17
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
我啪的一下一个sort()，很快嗷，然后一个遍历，直接通过，按传统编程，点到即止，我已经赢了。这时候他一个时间复杂度为 O(n)打过来，我大意了，没有闪，我说小力扣你不讲武德，来偷袭我这22岁的老同志，这好吗，这不好。我劝，这位小力扣耗子为汁，好好反思，不要再犯这样的聪明，小聪明啊。
class Solution { public int longestConsecutive(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); Arrays.sort(nums); int max = 0; for(int i = 0; i < nums.length; i++){ if(map.containsKey(nums[i] - 1)){ //如果哈希表中存放有nums[i] - 1的数 map.put(nums[i], map.get(nums[i] - 1) + 1); max = Math.max(max, map.get(nums[i] - 1) + 1); }else{ map.put(nums[i], 1); //如果不存在从1开始计数 max = Math.max(max, 1); } } return max; } }
使用set存储，无序可重复的特性。遍历数组，把连续的数全部删除记录最长的连续数就行。
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> numsSet = new HashSet<>(); for (Integer num : nums) { numsSet.add(num); } int longest = 0; for (Integer num : nums) { if (numsSet.remove(num)) { // 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,... int currentLongest = 1; int current = num; while (numsSet.remove(current - 1)) current--; currentLongest += (num - current); // 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,... current = num; while(numsSet.remove(current + 1)) current++; currentLongest += (current - num); // 搜索完后更新longest. longest = Math.max(longest, currentLongest); } } return longest; } }
原文：https://www.cnblogs.com/nobita/p/14287624.html