1.最长连续序列 

解题思路:

方法一：

1. • 首先对数组进行排序，这样我们可以直接比较相邻的元素是否连续。
2. • 使用一个变量 cur_cnt 来记录当前的连续序列长度。
3. • 遍历排序后的数组：
4.   如果当前元素与前一个元素相等，则跳过（因为相等的元素不会影响连续性）。
5.   如果当前元素与前一个元素相差 1，则当前元素是连续序列的一部分，增加计数器 cur_cnt。
6.  如果当前元素与前一个元素不连续，说明当前连续序列结束，更新最长连续序列 max，并重置 cur_cnt 为 1，准备重新计数。
7. • 在遍历结束后，返回最长的连续序列长度。

这种方法思维就就比较简单，而且最后的效率也很不错！

class Solution {public int longestConsecutive(int[] nums) {Arrays.sort(nums);int max =0;for(int i =0;i<nums.length;i++){int cur_cnt=1;while((i+1<nums.length&&nums[i+1]==nums[i]+1)||(i+1<nums.length&&nums[i+1]==nums[i])){if(nums[i+1]==nums[i]){i++;continue;}cur_cnt++;i++;}max=Math.max(max,cur_cnt);}return max;
}
}

 方法二：

对于数组中存在的连续序列，为了统计每个连续序列的长度，我们希望直接定位到每个连续序列的起点，从起点开始遍历每个连续序列，从而获得长度。

那么如何获取到每个连续序列的起点呢，或者说什么样的数才是一个连续序列的起点？
答案是这个数的前一个数不存在于数组中，因为我们需要能够快速判断当前数num的前一个数num - 1是否存在于数组中。

同时当我们定位到起点后，我们就要遍历这个连续序列，什么时候是终点呢？
答案是当前数num的后一个数nunm + 1不存在于数组中，因此我们需要能够快速判断当前数num的后一个数num + 1是否存在于数组中。

为了实现上述需求，我们使用哈希表来记录数组中的所有数，以实现对数值的快速查找。 

class Solution {public int longestConsecutive(int[] nums) {int res =0;//记录最长序列的长度Set<Integer> numSet =new HashSet<>();//记录所有的数值for(int num:nums){numSet.add(num);//将数组中的值加入到hash表中}int seqLen;//连续序列的长度for(int num:numSet){//如果当前的书是一个连续序列的起点，统计这个连续序列的长度if(!numSet.contains(num-1)){seqLen =1;while(numSet.contains(++num)) seqLen++;//不断查找连续序列，直到num的下一个数不存在数组中res =Math.max(res,seqLen);//更新最长连续序列长度}}return res;
}

2.单词拆分

• 将字符串 s 长度记为 n，wordDict 长度记为 m。为了方便，我们调整字符串 s 以及将要用到的动规数组的下标从 1 开始。
• 定义 f[i] 为考虑前 i 个字符，能否使用 wordDict 拼凑出来：当 f[i]=true 代表 s[1...i] 能够使用 wordDict 所拼凑，反之则不能。
• 不失一般性考虑 f[i] 该如何转移：由于 f[i] 需要考虑 s[1...i] 范围内的字符，若 f[i] 为 True 说明整个 s[1...i] 都能够使用 wordDict 拼凑，自然也包括最后一个字符 s[i] 所在字符串 sub。
• 我们可以枚举最后一个字符所在字符串的左端点 j，若 sub=s[j...i] 在 wordDict 中出现过，并且 f[j−1]=True，说明 s[0...(j−1)] 能够被拼凑，并且子串 sub 也在 wordDict，可得 f[i] = True。
• 为了快速判断某个字符是否在 wordDict 中出现，我们可以使用 Set 结构对 wordDict[i] 进行转存。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> set =new HashSet<>();for(String word:wordDict) set.add(word);int n =s.length();boolean[] f =new boolean[n+10];f[0]=true;for(int i =1;i<=n;i++){for(int j =1;j<=i&&!f[i];j++){String sub =s.substring(j-1,i);if(set.contains(sub))f[i]=f[j-1];}}return f[n];}
}

3.买卖股票的最佳时机III

class Solution {public int maxProfit(int[] prices) {int f1 =-prices[0],f2=0,f3=-prices[0],f4=0;for(int i =1;i<prices.length;i++){f1=Math.max(f1,-prices[i]);f2=Math.max(f2,f1+prices[i]);f3=Math.max(f3,f2-prices[i]);f4=Math.max(f4,f3+prices[i]);}return f4;}
}