leetcode数组刷题总结与分析_有n个数组,求n个数组中覆盖数组最多的序列

小结

数组题目中的一些方法与特征

关键字

• 有序
• 无序
• 从数组中任取几个数，还是从数组中确保顺序，取连续的几个数，例如：求连续数构成子数组，连续数最大值
• 从数组中取任意的数，还是从数组中取确定的数

方法

• 首先需要明白数组是一种连续存储的数据结构，因此可以按照顺序遍历真个数组，对于求数组中两个数的和，数组中的重叠元素，数组中连续子数组都可以采用多层遍历的方法，暴力法进行解决
• 上面的暴力法比较粗暴，时间复杂度往往是O(N^2 N^3)，因此需要进行改进 ；改进的策略可以总结为如下:

1. 数组是否可以先进行排序，再进行折半查找

2、数组是否在排序的基础上，进行双指针，向中部逼近,（尤其当数组需要求和的时候）；指针如何移动

3、若求某个范围，进行大小比较的时候，是否可以再双指针的基础上构建滑动窗口，来进行求解，关键是如何移动指针，就是通过移动指针来满足条件;例如：求两数的和=某值，求面积的最大值

4、采用快慢指针的方式,上面的为首尾指针，快慢指针可以将序列数组划分为若干部分，进行分析;在数组或字符串，链表的去重时可能会用到

5、数组是否可以空间换时间，将中间的计算结果进行存储，方便后来进行计算，例如hashMap存储中间计算的和，存储之前遍历的元素，关键是在hashMap中存储的是什么；

题目note

• 数组中的两个数的和----->
• 数组中三个树的和
• 排序数组中两个数的和
• 数组中连续子数组的和为k
• 数组中连续子数组中的和为k*n
• 数组中连续子数组的乘积小于k
• 数组的反转
• 成最多水的容器

……数组中元素的计算（子序列、任意元素）

题目一：两数之和

分析：要求求数组中两个数的和=target，关键是如何找到这两个数，也就是从数组中查找两个数的变形，那么首先可以使用暴力法

• 对于每个值nums[i]，可以遍历数组中的其他值，来进行判断，=两个值的和是否等于target 时间复杂度为O(n^2);
• 上面的复杂度太高，那么是否有某种方法进行改进呢？是否可以用空间换时间的策略，可以尝试map,先遍历下数组将每个值与其对应的索引放入到map值，再遍历下数组中的每个值，判断target-nums[i]是否在Map中；那么时间复杂度为O(n)，空间复杂度为O(n)
• 扩展:若没有要求求出数组的索引，就是单纯的求数组中值的组合，办么我们可以先对数组进行排序，再定义两个指针left,right，初始化为数组的首元素与末尾元素，进行夹逼的方式进行逼进，若两个值>target则right左移一位，若两个值<target则left右移一位；直到left<right

package AarrayProblem;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/3/29 0029  22:32
 * 数组中两数之和
 *
 *   在数组中求数组的和
 *          这其实也是在数组中查找元素的变形，关键是在数组中查找两个元素，
 *          这两个元素的和要满足某种要求
 *
 *
 *            （1） 可以遍历对于每个确定的值nums[i]遍历整个数组，若数组中存在target-nums[i]则存在
 *                     时间复杂度为o(n^2)
 *
 *             (2) 上面的时间复杂度比较大，我们是否可以尝试采用空间换时间的策略：
 *                  我们需要一种更有效的方法来检查数组中是否存在目标元素，因为结果是返回索引，那么我们可以
 *                  使用  value--index 的map数据结构，
 *                  先遍历数组将所有 value-index加入到hashMap中，然后再计算在 hashMap中是否包含target-arr[i]
 *                  时间复杂度：O（n)  空间复杂度：O（n)
 *
 *             （3）对于数组我们是否可以采用先对其排序，然后再进行操作
 */
public  class Problem1 {
   


    //暴力遍历整个数组
    //时间复杂度：O（n^2)
    //对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费O(N)时间
    public int[] twoSum(int[] nums, int target) {
   

        int[] rs= new int[2];
        int length = nums.length;

        for(int i=0;i<length;i++){
   
            for(int j=i+1;j<nums.length;j++){
   
                if(nums[i]+nums[j]==target){
   
                    rs[0]=i;
                    rs[1]=j;
                }
            }

        }
        return rs;
    }



    //使用一个hashMap以空间换时间
    //一个简单的实现使用了两次迭代，在第一次迭代中，我们将每个元素的值和它的索引添加到表中
    //然后在第二次迭代中，我们检查每个元素所对应的目标(target-nums[i]）是否存在于表中；
    //时间复杂度：O(n);我们把包含有n个元素怒的列表遍历两次，由于哈希表将查找时间缩短到O(1)，所以时间爱你复杂度为O(N)
    //空间复杂度:O(N)
    //小结：当时间复杂度比较大的时候，我们可以思考是否可以用空间换时间解决
    //那么常用的空间可以采用:HashMap、queueu、statck、priorityQueur
    //在以后的问题中要想清楚每种何时采用什么样的数据结构
    public int[] twoSum1(int[] nums, int target){
   
        Map<Integer,Integer> map = new HashMap<>();
        //将value---key存放到map中
        for(int i=0;i<nums.length;i++){
   
            map.put(nums[i],i);
        }

        //遍历
        for(int i=0;i<nums.length;i++){
   
            //保证 不是同一个数 并且两个数的和=target
            if(map.containsKey(target-nums[i])&&(map.get(target-nums[i])!=i)){
   
                return new int[] {
   i,map.get(target-nums[i])};
            }
        }
       return null;
    }



    //一遍hash表
    //在遍历hash表的时候就判断在hash表中是否包含 target-value值
    public int[] twoSum2(int[] nums, int target){
   
        Map<Integer,Integer> map = new HashMap<>();
        //遍历数组
        for(int i=0;i<nums.length;i++){
   

            int value = nums[i];
            if(map.containsKey(target-value)){
   
                return new int[]{
   i,map.get(value)};
            }
            map.put(nums[i],i);

        }
        return null;

    }


    //这种方法也叫双指针法
    //在leetcode4中可以采用这种方法
    //是否可以先对数组进行排序
    //要返回的是索引的位置这意味着不能对数组进行排序
    //若没有要求返回的是数组的索引位置而就是返回数组的选值的问题，那么就可以采用这种方法
    public int[] twoSum3(int[] nums, int target){
   

        //先进行排序
        Arrays.sort(nums);

        int left =0;
        int right = nums.length-1;

        while(left<right){
   
            int value = nums[left]+nums[right];
            if(value == target){
   
                return new int[] {
   left,right};
            }else if(value>target){
   //两个计算的值大于taRGET则说明，right向后退意味
                right--;
            }else{
   
                left++;
            }
        }

        return null;

    }


    public static void main(String[] args) {
   
        Problem1 problem1 = new Problem1();
        int[] arr = {
   3,2,4};
        int[] rs = problem1.twoSum3(arr,6);
    }



}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

题目15、三数的和

• 首先，受题目一的影响，可以采用暴力法，三层遍历，穷举每种可能，进行判断(但这种方法 在测试的时候超时);时间复杂度为O(N^3)
• 可以采用题目一种的双指针的方法，遍历每个值nums[i]，定义两个指针left和right初始值分别为i+1和nums.length-1，每次判断nums[left]+nums[right]+nums[i]的和是否为target，否则进行指针移动，注意在移动的时候要注意去重,时间复杂度为O(N^2)

package AarrayProblem;

import java.util.*;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/3/29 0029  23:28
 *
 * 三数之和
 */
public  class Problem15 {
   


    //暴力方法：三层循环核心从数组中任意挑选三个数字
    //难点：不包含重复的三元数组
    //固定一个转换为 二个数的和
    //通过 311/313个测试用例
    //
    //暴力破解的方法失效:超出时间限制】

    public List<List<Integer>> threeSum(int[] nums) {
   

        int length = nums.length;

        List<List<Integer>> rs = new ArrayList<>();
        //数组中任意三个树的和
        for(int i=0;i<nums.length;i++){
   
            for(int j=i+1;j<nums.length;j++){
   
                for(int t=j+1;t<nums.length;t++){
   
                    //进行判断
                    if((nums[i]+nums[j]+nums[t]==0)){
   
                        ArrayList<Integer> r = new ArrayList<>();
                        r.add(nums[i]);
                        r.add(nums[j]);
                        r.add(nums[t]);
                        Collections.sort(r);

                        if(!rs.contains(r))
                        rs.add(r);
                    }
                }
            }

        }
        return rs;
    }


    //先确定一个数，在去求另外连个数的和
    //简化成leetcode2
    //显然不能用hashMap：使用hashMap如何使用
    //存在超时限制
    public List<List<Integer>> threeSum1(int[] nums){
   

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

        Map<Integer,Integer> map = new HashMap<>();

        //首次遍历将所有元素加入到HashMap中
        //若两个元素重复则可能覆盖
        //则将索引作为key，值作为vaklue
        for(int i=0;i<nums.length;i++){
   
            map.put(i,nums[i]);
        }

        for(int i=0;i<nums.length;i++){
   
            for(int j=i+1;j<nums.length;j++){
   

                map.remove(i);
                map.remove(j);

                int value = 0-nums[i]-nums[j];
                if(map.containsValue(value)){
   //在map中包含，并且不包含当前遍历的map[i],map[j]
                    //这里存在问题
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(nums[i]);
                    arrayList.add(nums[j]);
                    arrayList.add(value);
                    Collections.sort(arrayList);
                    if(!list.contains(arrayList))
                    list.add(arrayList);
                }
                map.put(i,nums[i]);
                map.put(j,nums[j]);
            }
        }
        return list;




    }



    //采用双指针法：（夹逼法）——。
    //1、先对数组进行排序
    //2、边里数组的每个元素：nums[i]
     //2.1、定义连个初始指针 left------>nums[i+1]
                          // right------>nums.length-1
     //若nums[left]+nums[right]+arr[i]==0 ;为了防止重复元素的出现 去重，while(left<right && nums[left]==nums[left+1]) left++;
    //若value<0则left++
    //若value>0 则rtight--(和小了则单方面移动右指针）
    public List<List<Integer>> threeSum2(int[] nums){
   



        List<List<Integer>> rs = new ArrayList<>();
        int lenght = nums.length;
        if(lenght<3) return rs;

        //1、对数组排序
        Arrays.sort(nums);

        for(int i=0;i<lenght;i++){
   


            //需要判断，去重
            //当连续的两个数相等时取后面的一个数
            if(i>0&&nums[i]==nums[i-1]) continue;


            //左右两个指针锁对应的值的和应该为value
            //定义两个指针
            int left = i+1;
            int right = lenght-1;
            while(left<right) {
   
                int sum = nums[i]+nums[left]+nums[right];
                if (sum==0){
   

                    //添加元素
                    rs.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--;
                }else if(sum>0){
   //当前的计算结果的值大于value，则应该将右指针做移动
                    right--;
                }else if(sum<0){
   //当前计算结果的值小于value，则应该将左指针右移动，选择更大的数
                    left++;
                }
            }

        }
        return rs;


    }


    public static void main(String[] args) {
   
        Problem15 problem15 = new Problem15();
        int[] arr = {
   0,0,0};

        List<List<Integer>> RS =problem15.threeSum2(arr);
        System.out.println(RS);

    }



}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

17、四数之和

分析：可以使用暴力法：四层循环O(N^4)
参考：两数之和，三数之和，是否可以借助指针呢,两个指针遍历。
这里的难点是如何去重;

• 使用四个指针(i<j<left<right)，固定最小的i和j，left=j+1,rigth=length-1
• 使用双层循环，遍历所有i和j;
• 使用动态指针left和right根据sum的和nums[i]+nums[j]+nums[left]+nums[right]调整数组的和；若和大于target则right左移动，若小于target则left右移动
• 当left和righ相遇时，表示本轮遍历已经结束，开始下一轮
  如何解决重复问题
  确保移动指针后，对应的数字要发生改变
  • 当i和j每次更新的时候，要进行判断，若和前一次相等则continue
  • 当sum=target，时需要移动left和right的指针，此时也需要进行判断数字是否相等，不断判断，直到找到数字不相等指针所在位置

package AarrayProblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/3/31 0031  16:14
 * 四数之和
 */
public class Problem18 {
   
    //这道题目中要求：任取四个数，因此可以对数组进行排序等操作
    //采用暴力的算法：O（n^4)
    //是否可以采用双指针的做法：
    //先对数组进行排序
    //然后
    //核心如何去重，去重
    public List<List<Integer>> fourSum(int[] nums, int target) {
   
        //首先对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();

        //假如数组的长度小于4则返回空
        if(nums.length<4){
   return list;}

        for(int i=0;i<nums.length-3;i++){
   
            //当前后两次的值相等的时候跳过;确保nums[i]的值发生了改变
            //若当前的元素在前面遍历过程中出现过则跳过
            if(i>=1&&nums[i]==nums[i-1]) continue;

            for(int j=i+1;j<nums.length-2;j++){
   

                //当前后两次的值相等的时候跳过
                //若当前元素在前面遍历过程中出现则跳过
               if(j>i+1&&nums[j]==nums[j-1]) continue;
               //左右指针初始化
               int left = j+1;
               int right = nums.length-1;
               //动态调整左右指针
               while(left<right) {
   
                    //计算和
                   int sum = nums[i] + nums[j] + nums[left] + nums[right];
                   //假如和的值为target
                   if (sum == target) {
   
                       List<Integer> l = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                       list.add(l);
                       //去除重复元素
                       while(left<right&&nums[left]==nums[left+1]) left++;
                       while(left<right&&nums[right]==nums[right-1]) right--;
                       //最后要加上，因为前面的判断是当前元素和下一个元速进行判断
                       left++;
                       right--;
                   } else if (sum > target) {
   //假如sum>target，则需要将右指针左移

                       //这里也可以进行判断:当前元素和前一个元素相等，则right--
                       //这里不假循环判断也行
                       while(left<right&&nums[right]==nums[right-1]) right--;
                       right--;

                   } else {
   
                       while(left<right&&nums[left]==nums[left+1]) left++;
                        left++;
                   }
               }

            }
        }

        return list;
    }


    public static void main(String[] args) {
   
        Problem18 problem18 = new Problem18();
//        int[] arr = {-3,-2,-1,0,0,1,2,3};
        int[] arr = {
   -1,0,1,2,-1,-4};

        List<List<Integer>> rs;
        rs=problem18.fourSum(arr,-1);
        System.out.println(rs);

    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

16、最接近三数之和

分析：与上提类似，只不过上提中要求三数的和是某个确定的值，而此题中，要求三个数最接近某个值，因为其类似性，因此我们可以采用相同的思路

• 可以采用暴力法:三层遍历整个数组，穷举每种可能，进行差值的比较，若发现插值小，则进行更新
• 可以采用双指针法:
  • 先对数组进行排序 时间复杂度为O(nlogn)
  • 在数组nums中，进行遍历，每遍历一个值利用其下标i，形成一个固定值nums[i]
  • 再适应前指针指向start=i+1处，后指针指向end=nums.length-1也就是结尾处
  • 根据sum=nums[i]+nums[start]+nums[end的结果，判断sum与目标target的距离，如果更近则更新结果ans
  • 同时判断sum与target的大小关系，因为数组有序，如果sum>target，则ebd--,如果sum<target则start++</