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