JAVA-高频面试题汇总:数组（下）

客官°小女子只卖身不卖艺 2022-10-27 01:54 293阅读 0赞

## 前言 ##

为了让小伙伴们更好地刷题,我将所有leetcode常考题按照知识点进行了归纳。

## 高频题汇总: ##

[JAVA-高频面试题汇总:动态规划][JAVA-]  
[JAVA-高频面试题汇总:字符串][JAVA- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]  
[JAVA-高频面试题汇总:回溯][JAVA- 4]  
[JAVA-高频面试题汇总:链表][JAVA- 5]  
[JAVA-高频面试题汇总:数组（上）][JAVA- 6]

#### JAVA-高频面试题汇总:数组（下） ####

接下来还会进行其他模块的总结,有一起在准备暑期实习的JAVA后端的伙伴可以一起交流!  
小编微信: Apollo\_\_\_quan

--------------------

## 目录 ##

1.  数组中数字出现的次数（剑指）
2.  数组中数字出现的次数 II（剑指）
3.  和为s的连续正数序列（剑指）
4.  和为s的两个数字（剑指）
5.  数组中重复的数字（剑指）
6.  构建乘积数组（剑指）
7.  三数之和
8.  四数之和
9.  二进制中1的个数（剑指）)
10. 不用加减乘除做加法（剑指） 
11. 求1+2+…+n（剑指）

--------------------

##### 11.[数组中数字出现的次数（剑指）][Link 1] #####

![image-20210203115537830][]

**思路**

1.将所有数异或，会剩下两个数，其他数相消。0^0=0； 0^1=1； 1^0=1； 1^1=0。

2.剩下两个数区分不出，所以需要将两个数分在不同的组，两组各得出一个。

3.先得出这两个数某一位数不同，然后根据这个进行分组。

class Solution { 
        public int[] singleNumbers(int[] nums) { 
            //用于将所有的数异或起来
            int k = 0;
            
            for(int num: nums) { 
                k ^= num;    //k即为剩下的两个数的异或
            }
            
            //获得k中最低位的1
            int mask = 1;
    
    
            while((k & mask) == 0) {  //对k进行位与，与0001，0010，0100这样子与，得到非0时即为不同的位，根据此将两个数分到不同组
                mask <<= 1; 
            }
            
            int a = 0;
            int b = 0;
            
            for(int num: nums) { 
                if((num & mask) == 0) { 
                    a ^= num; //分组1进行异或后得到a
                } else { 
                    b ^= num; //分组2进行异或后得到b
                }
            }
            return new int[]{ a, b};
        }
    }

##### 12.[数组中数字出现的次数 II（剑指）][II] #####

![image-20210203151216123][]  
**思路**

1.遍历数组，记录所有数字的每一位出现次数，并对3求余，便可知道哪些位只出现了1次

2.根据这些位还原出数字

时间复杂度 O(N) ： 其中 NN位数组 nums的长度；遍历数组占用O(N) ，每轮中的常数个位运算操作占用 O(1)。  
空间复杂度 O(1) ： 数组 counts长度恒为 32 ，占用常数大小的额外空间。

class Solution { 
        public int singleNumber(int[] nums) { 
            int[] counts = new int[32]; //int一共4字节，32位
            for(int num : nums) { 
                for(int j = 0; j < 32; j++) { 
                    counts[j] += num & 1; //记录每个数字的每一位出现次数
                    num >>>= 1;
                }
            }
            int res = 0;
            for(int i = 0; i < 32; i++) {  
                res <<= 1;
                res |= counts[31 - i] % 3; //还原出数字
            }
            return res;
        }
    }

##### 13.[和为s的连续正数序列（剑指）][s] #####

![image-20210203164710619][]

**思路**

滑动窗口（双指针）

![image-20210203165234288][]

![image-20210203165256081][]

class Solution { 
        public int[][] findContinuousSequence(int target) { 
            int i = 1, j = 2, s = 3; //初始化i、j最左相邻
            List<int[]> res = new ArrayList<>();
            while(i < j) { 
                if(s == target) {    //若等于目标值
                    int[] ans = new int[j - i + 1]; //创建新数组记录下此时窗口中的值
                    for(int k = i; k <= j; k++)
                        ans[k - i] = k;
                    res.add(ans);  //将数组加入res
                }
                if(s >= target) {  //大于等于目标值时
                    s -= i;  //从s中减去i
                    i++;  //窗口左边界移动
                } else { 
                    j++; //小于目标值时右边界右移
                    s += j;
                }
            }
            return res.toArray(new int[0][]);
        }
    }

##### 14.[和为s的两个数字（剑指）][s 1] #####

![image-20210203174054244][]

**思路**

和上一题相区别，滑动窗口是两个指针一起从左往右，该题为一左一右往中间

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            int i = 0, j = nums.length - 1; //初始化i最左，j最右，与上一题区别
            while(i < j) { 
                int s = nums[i] + nums[j];
                if(s < target) i++;  //小于target则i右移
                else if(s > target) j--;  //大于target则j左移
                else return new int[] {  nums[i], nums[j] };
            }
            return new int[0]; //若都没有输出空数组[]，元素个数为0个，实际在内存开空间了，但大小为0
        }
    }

##### 15.[数组中重复的数字（剑指）][Link 2] #####

![image-20210203175936615][]

**思路**

原地置换

如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回

时间复杂度O(N)

空间复杂度O(1)

class Solution { 
        public int findRepeatNumber(int[] nums) { 
            int temp;
            for(int i=0;i<nums.length;i++){ 
                while (nums[i]!=i){  //遇到不对应的数
                    if(nums[i]==nums[nums[i]]){ 
                        return nums[i];
                    }
                    temp=nums[i]; //交换两个数，进入下一次循环（判断交换后的新nums[i]是否等于i）
                    nums[i]=nums[temp];
                    nums[temp]=temp;
                }
            }
            return -1;
        }
    }

##### 16.[构建乘积数组（剑指）][Link 3] #####

![image-20210203181332015][]

**思路**

根据表格的主对角线（全为 11 ），可将表格分为 **上三角** 和 **下三角** 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 **不使用除法** 就获得结果。

![image-20210203213753812][]

class Solution { 
        public int[] constructArr(int[] a) { 
            if(a.length == 0) return new int[0]; //返回空数组
            int[] b = new int[a.length];
            b[0] = 1;
            int tmp = 1; 
            for(int i = 1; i < a.length; i++) {  //上三角，从第二行（i=1）开始遍历到第五行（i=4）
                b[i] = b[i - 1] * a[i - 1];
            }
            for(int i = a.length - 2; i >= 0; i--) {  //下三角，从第四行（i=3）遍历到第一行（i=0）
                tmp *= a[i + 1];
                b[i] *= tmp;
            }
            return b;
        }
    }

##### 17.[三数之和][Link 4] #####

![image-20210130114836551][]

**思路**

![image-20210206224810478][]

class Solution { 
        public List<List<Integer>> threeSum(int[] nums) { 
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int k = 0; k < nums.length - 2; k++){ 
                if(nums[k] > 0) break; //最小的大于0，加上后面的肯定也>0
                if(k > 0 && nums[k] == nums[k - 1]) continue; //跳过相同的nums[k]
                int i = k + 1, j = nums.length - 1;
                while(i < j){ 
                    int sum = nums[k] + nums[i] + nums[j];
                    if(sum < 0){ 
                        while(i < j && nums[i] == nums[++i]); //太小i右移
                    } else if (sum > 0) { 
                        while(i < j && nums[j] == nums[--j]); //太大j左移
                    } else { 
                        res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                        while(i < j && nums[i] == nums[++i]); //相等则加入res，i右移j左移
                        while(i < j && nums[j] == nums[--j]);
                    }
                }
            }
            return res;
        }
    }

##### 18.[四数之和][Link 5] #####

![image-20210203221543322][]

**思路**

四数之和与前面三数之和的思路几乎是一样的，这里其实就是在前面的基础上多添加一个遍历的指针而已。  
使用四个指针(a<b<c<d)。固定最小的a和b在左边，c=b+1,d=\_size-1 移动两个指针包夹求解。  
保存使得nums\[a\]+nums\[b\]+nums\[c\]+nums\[d\]==target的解。偏大时d左移，偏小时c右移。c和d相  
遇时，表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环，当b循环结束后。  
a++，进入下一轮a循环。 即(a在最外层循环，里面嵌套b循环，再嵌套双指针c,d包夹求解)。

class Solution { 
        public List<List<Integer>> fourSum(int[] nums, int target) { 
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int k = 0; k < nums.length - 3; k++){ 
                if(nums[k] + nums[k+1] + nums[k+2] +nums[k+3] > target){  //这里和三数之和重点区别
                   break;
               } 
                if(k > 0 && nums[k] == nums[k - 1]) continue; //跳过k相同的，注意k>0条件，说明不是第一次遇到
                for(int h = k + 1; h < nums.length - 2; h++){ 
                    
                    if(h > (k + 1) && nums[h] == nums[h - 1]) continue;//跳过h相同的，注意h > (k + 1)条件，说明不是第一次遇到
                    int i = h + 1, j = nums.length - 1;
                    while(i < j){ 
                        int sum = nums[k] + nums[h] + nums[i] + nums[j];
                        if(sum < target){ 
                            while(i < j && nums[i] == nums[++i]); //太小i右移
                        } else if (sum > target) { 
                            while(i < j && nums[j] == nums[--j]); //太大j左移
                        } else { 
                            res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[h], nums[i], nums[j])));
                            while(i < j && nums[i] == nums[++i]); //相等则加入res，i右移j左移
                            while(i < j && nums[j] == nums[--j]);
                        }
                    }
                }
            }
            return res;
        }
    }

##### 19.[二进制中1的个数（剑指）][1] #####

![image-20210203234003297][]

**思路**

基础题，逐位判断

public class Solution { 
        public int hammingWeight(int n) { 
            int res = 0;
            while(n != 0) { 
                res += n & 1;
                n >>>= 1;
            }
            return res;
        }
    }

##### 20.[不用加减乘除做加法（剑指）][Link 6] #####

![image-20210204094828228][]

**思路**

![image-20210204101126547][]

class Solution { 
        public int add(int a, int b) { 
            while(b != 0){  //进位为0时跳出循环
            int temp = (a & b) << 1; //记录进位
            a = a ^ b; //将a换位无进位和
            b = temp; //将b换为进位
            }
            return a;
        }
    }

##### 21.[求1+2+…+n（剑指）][1_2_n] #####

![image-20210204101423423][]

**思路**

通过逻辑与操作，A && B，当A不成立时B被短路。

A是递归条件控制递归何时停止，所以n > 1。

B是递归操作，同时B应在A条件下时刻满足，于是sumNums(n - 1) > 0，其中0换成-1等其实也可。

且最终返回的是个boolean类型，这个要注意

![image-20210204102537295][]

class Solution { 
        int res = 0;
        public int sumNums(int n) { 
            boolean x = n > 1 && sumNums(n - 1) > 0; //最后一次递归n=1，后面的短路，但不影响res累计
            res += n; //将每次的n累加
            return res;
        }
    }

## 总结 ##

数组（下）整理完毕，其余类型  
[JAVA-高频面试题汇总:动态规划][JAVA-]  
[JAVA-高频面试题汇总:字符串][JAVA- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]  
[JAVA-高频面试题汇总:回溯][JAVA- 4]  
[JAVA-高频面试题汇总:链表][JAVA- 5]  
[JAVA-高频面试题汇总:数组（上）][JAVA- 6]

[JAVA-]: https://blog.csdn.net/weixin_44273302/article/details/112000020
[JAVA- 1]: https://blog.csdn.net/weixin_44273302/article/details/112436689
[JAVA- 2]: https://blog.csdn.net/weixin_44273302/article/details/112142969
[JAVA- 3]: https://blog.csdn.net/weixin_44273302/article/details/112200568
[JAVA- 4]: https://blog.csdn.net/weixin_44273302/article/details/113423696
[JAVA- 5]: https://blog.csdn.net/weixin_44273302/article/details/113529501
[JAVA- 6]: https://blog.csdn.net/weixin_44273302/article/details/113575810
[Link 1]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jie-di-qi-jiang-jie-fen-zu-wei-yun-suan-by-eddievi/
[image-20210203115537830]: /images/20221024/86417bcae01c4736bc278976ace8de91.png
[II]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[image-20210203151216123]: /images/20221024/144579a5c77540e4bee306eab83b0514.png
[s]: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/jian-zhi-offer-57-ii-he-wei-s-de-lian-xu-t85z/
[image-20210203164710619]: /images/20221024/e9af7a3216444ecc90263dbccded9418.png
[image-20210203165234288]: /images/20221024/fa010b05bc6a43779f7b1d823cab2a2f.png
[image-20210203165256081]: /images/20221024/e5c2930f3f9443379f61cb0389fccf30.png
[s 1]: https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/solution/mian-shi-ti-57-he-wei-s-de-liang-ge-shu-zi-shuang-/
[image-20210203174054244]: /images/20221024/d6a4af9891864a3599a5443ab2f45a10.png
[Link 2]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/yuan-di-zhi-huan-shi-jian-kong-jian-100-by-derrick/
[image-20210203175936615]: /images/20221024/a2ea3a203a7144888bebd281fec0c651.png
[Link 3]: https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
[image-20210203181332015]: /images/20221024/70954f4957f64b17b74ae89ef7751cc5.png
[image-20210203213753812]: /images/20221024/c3c5d3cbc2cb43fbb27168eaf1d4087e.png
[Link 4]: https://leetcode-cn.com/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/
[image-20210130114836551]: /images/20221024/78f2de0166ce45ee8c51614ff251cd02.png
[image-20210206224810478]: /images/20221024/6f034499ab2d47e4929d6c7b0c2efb31.png
[Link 5]: https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/
[image-20210203221543322]: /images/20221024/6f559055176b4f8082b2935210999dee.png
[1]: https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
[image-20210203234003297]: /images/20221024/a703a6c0eb5044ad9e3be59af14ccd83.png
[Link 6]: https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/
[image-20210204094828228]: /images/20221024/d28dd3e3546f41d2b95ff0dd10d49fca.png
[image-20210204101126547]: /images/20221024/7e648da8ca844071b4d8b3d4ca4da9d6.png
[1_2_n]: https://leetcode-cn.com/problems/qiu-12n-lcof/solution/mian-shi-ti-64-qiu-1-2-nluo-ji-fu-duan-lu-qing-xi-/
[image-20210204101423423]: /images/20221024/1f7770709597465cad86bd4666f24d6c.png
[image-20210204102537295]: /images/20221024/c4e629b35b324fbe9405fd93eb83aee3.png