算法面试——哈希表：两数之和、三数之和、最长连续序列

哈希表以 O(1) 的查找速度解决快速判断元素是否存在的问题。

一、两数之和

publicint[]twoSum(int[]nums,inttarget){Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){intcomplement=target-nums[i];if(map.containsKey(complement)){returnnewint[]{map.get(complement),i};}map.put(nums[i],i);}returnnewint[]{-1,-1};}

二、三数之和

publicList<List<Integer>>threeSum(int[]nums){Arrays.sort(nums);List<List<Integer>>result=newArrayList<>();for(inti=0;i<nums.length-2;i++){if(i>0&&nums[i]==nums[i-1])continue;intleft=i+1,right=nums.length-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==0){result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}elseif(sum<0)left++;elseright--;}}returnresult;}

三、最长连续序列

publicintlongestConsecutive(int[]nums){Set<Integer>set=newHashSet<>();for(intnum:nums)set.add(num);intmaxLen=0;for(intnum:set){// 只从连续序列的起点开始找if(!set.contains(num-1)){intcur=num,len=1;while(set.contains(cur+1)){cur++;len++;}maxLen=Math.max(maxLen,len);}}returnmaxLen;}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！