算法面试——哈希表：两数之和、三数之和、最长连续序列
哈希表以 O(1) 的查找速度解决快速判断元素是否存在的问题。一、两数之和publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermapnewHashMap();for(inti0;inums.length;i){intcomplementtarget-nums[i];if(map.containsKey(complement)){returnnewint[]{map.get(complement),i};}map.put(nums[i],i);}returnnewint[]{-1,-1};}二、三数之和publicListListIntegerthreeSum(int[]nums){Arrays.sort(nums);ListListIntegerresultnewArrayList();for(inti0;inums.length-2;i){if(i0nums[i]nums[i-1])continue;intlefti1,rightnums.length-1;while(leftright){intsumnums[i]nums[left]nums[right];if(sum0){result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left;right--;}elseif(sum0)left;elseright--;}}returnresult;}三、最长连续序列publicintlongestConsecutive(int[]nums){SetIntegersetnewHashSet();for(intnum:nums)set.add(num);intmaxLen0;for(intnum:set){// 只从连续序列的起点开始找if(!set.contains(num-1)){intcurnum,len1;while(set.contains(cur1)){cur;len;}maxLenMath.max(maxLen,len);}}returnmaxLen;} 觉得有用的话点赞 关注【张老师技术栈】吧
)
