Longest Consecutive Sequence
https://leetcode.com/problems/longest-consecutive-sequence/description/
HashMap
https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted
public class Solution {
public int longestConsecutive(int[] nums) {
int max = 0;
if(nums == null || nums.length == 0){
return max;
}
Map<Integer, Integer> map = new HashMap<>();
for(Integer e : nums){
if(!map.containsKey(e)){
int left = map.containsKey(e - 1)? map.get(e - 1) : 0;
int right = map.containsKey(e + 1)? map.get(e + 1) : 0;
int sum = 1 + left + right;
map.put(e, sum);
max = Math.max(max, sum);
map.put(e - left, sum);
map.put(e + right, sum);
}else{
continue;
}
}
return max;
}
}
set.contains(value) return boolean value!!!
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0) return 0;
Set<Integer> set = new HashSet<Integer>();
for(int num: nums) set.add(num);
int max = 1;
for(int num: nums) {
if(set.remove(num)) {//num hasn't been visited
int val = num;
int sum = 1;
while(set.remove(val-1)) val--;
sum += num - val;
val = num;
while(set.remove(val+1)) val++;
sum += val - num;
max = Math.max(max, sum);
}
}
return max;
}