蓝桥杯-动态规划专题-子数组系列，双指针

目录

一、单词拆分?

二、环绕字符串中唯一的子字符串

双指针-三数之和

ArrayList(Arrays.asList(array))

四、四数之和（思路和三数之和一样，只是多了一层循环）

一、单词拆分?

1.状态表示

dp[i]:到达i位置结尾，能否被dict拆分

最难的我认为到现在为止就是选择状态如何表示

dp[i]:[0,i]区间内的字符串，能否被字典中的单词拼接而成

2.状态转移方程

设置j为i位置位置最后一个单词的第一个字母

那么dp[i]->dp[j-1]==true&&s[j,i]这个字符串在dict之中

3.初始化

dp[0]=s[0]在dict中,就是true。

dp[m+1]:直接扩大一个格子，这样他就不需要考虑边界

我们可以让s这个字符串前面加一个空格

这样字符串就会往后挪动一个空格

4.顺序是

从左到右

5.返回值

dp[n]

优化：既然可以有重复，重复可以一直使用，那么可以人工把这个dict中去重放到set中，这样，重复的问题就可以不用去考虑了

简单来说，包头不包尾巴。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       Set<String> hash=new HashSet(wordDict);
       int m=s.length();  
       boolean []dp=new boolean[m+1];
       //加一个占位符，可以处理下标的映射关系
       s=" "+s;
       dp[0]=true;
       
//遍历从1开始，是因为不去考虑边界条件区域
//dp[i]:[0,i]区间内的字符串，能否被字典中的单词拼接而成
//设置j为i位置位置最后一个单词的第一个字母，i+1的原因是往后推了一个格子。
//--的原因是什么呢？他这个过程，我认为像是找最后一个单词的第一个字母是什么，所以才会有--的原因，是因为--从最后开始遍历去寻找
//另外，他那个sub是包头不包尾巴，所以说那个需要到i+1,但是实际也就是j-i
       for(int i=1;i<=m;i++){
           for(int j=i;j>=1;j--)
           {
               if(dp[j-1]&& hash.contains(s.substring(j,i+1))){
                   dp[i]=true;
                   //假如有一个方式匹配成功了，那么就不需要别的方式了，可以直接跳出
                   break;
               }
           }
       }
return dp[m];
    }
}

二、环绕字符串中唯一的子字符串

1.状态表示

dp[i]:到达i为止，有dp[i]个非空字符串在base中存在过

2.状态转移方程

假如说连接的情况只有两种

一种是后面减去前面的等于一

第二种就是前面的是z后面的是a相差25

假如她这个连接不起来，就是自然的单独一个

这个时候我已经看第二个实例：在想一个问题，可不可以把它放到set里面去重，假如去重来会怎么样？但是我又想到一个问题，假如去重了，那么假如这种abcdefghigklmnopqrstuvwxyza ，一圈之后还有个a，怎么办，那么这样就不能使用传统意义上的去重，不妨使用数组（26个字母，就26个容量），然后去更新数组的值，假如a[0]==xx,那么下次在第n次的时候会再次到达，a[0]更新到最大值。

双指针-三数之和

三数之和：采用双指针的操作。

class Solution {
      public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>ret=new ArrayList<>();
        int m=nums.length;

        Arrays.sort(nums);
        for(int i=0;i<m;){
            int left=i+1,right=m-1;
            int a=nums[i];
            while(left<right){
                if(nums[left]+nums[right]<-a){
                    left++;
                }
                else if(nums[left]+nums[right]>-a){
                    right--;
                }
                else{
//Arrays.asList():这个方法是什么意思呢？
//这个方法的意思是将数组转化成List集合的方法。也就是说把数组这个三个元素装入List集合里面
//（1）该方法适用于对象型数据的数组（String、Integer...）

//（2）该方法不建议使用于基本数据类型的数组（byte,short,int,long,float,double,boolean）
//这个方法是使用包装类(Integer等)

//（3）该方法将数组与List列表链接起来：当更新其一个时，另一个自动更新

//（4）不支持add()、remove()、clear()等方法

  ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
//缩小区间继续寻找
                    left++;
                    right--;
//对于去重：left是往右走，那么就是他和上一个看是不是一样的。
                    while(left<right&&nums[left]==nums[left-1])left++;
//right是往左走，他和右边那个是不是一样。
                    while(left<right&&nums[right]==nums[right+1])right--;

                }}
                //本身的i也需要去去重，i<m，如果i和前一个i-1一样，那么就去再次去重
                i++;
                while(i<m && nums[i]==nums[i-1])i++;
        }
        return ret;
}
}

因为left+right已经不可能会出现小于0的情况

其次我们要熟悉两个方法

我本是对JAVA的集合方面不是很熟系，所以我会在下面再去写一些我不熟悉的东西

List<List<Integer>>ret=new ArrayList<>();

Arrays.asList:这个方法，只推荐用于遍历，而不推荐进行删改等操作，它是把数组元素转换成集合，这种方法，你在修改他的时候，也会影响到原先的数组，所以推荐是（不去用它删除，只去遍历）

ArrayList(Arrays.asList(array))

与?Arrays.asList?方法一样，我们还可以使用?ArrayList<>(Arrays.asList(array))?来从 Array 创建一个 List。

但是，与上面的方法不一样的是，使用这个方法创建的 List 是一个从老的 Array 中数据拷贝过来的，这个新的 List 与老的 Array 不相干，对新 List 中数据的操作不会影响到老的 Array 中的数据。

使用这种方法创建的 List 是可以对 List 中的元素进行添加和删除操作的。

https://www.cnblogs.com/huyuchengus/p/15132032.html

一个关于ArrayList(Array.asList(array))和普通的Array.asList()的区别

四、四数之和（思路和三数之和一样，只是多了一层循环）

class Solution {
 public  static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>>ret=new ArrayList<>();
    int m=nums.length;
    Arrays.sort(nums);
    for(int i=0;i<m;){
        for(int j=i+1;j<m;){
            int left=j+1;
            int right=m-1;
            long n=(long)target-nums[i]-nums[j];
            while(left<right){
                if(nums[left]+nums[right]>n){
                    right--;
                }
                else if(nums[left]+nums[right]<n){
                    left++;
                }
                else{
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[i], nums[j], nums[right])));
                        left++;
                        right--;
                        while (nums[left] == nums[left - 1] && left < right) left++;
                        while (nums[right] == nums[right + 1] && left < right) right--;
                    }
                }

            j++;
            while(j<m&&nums[j]==nums[j-1]&&j<m){
                j++;
            }
        }
        i++;
        while(i>0&&i<m&&nums[i]==nums[i-1])i++;
    }
    return ret;
}
    }

这里使用long是为了处理一组数据，因为int的数值有一定范围，所以不可以用int去承载那么多的数，所以使用long

这里我还要讲一个

if ?

else if

else

是说假如if不成立，看else if成不成立，但假如说if成立的情况下，这层循环结束，开始下一次循环，不执行下面逻辑的判断