一、整数
1. 整数基础知识
a. 整数概念
- 整数是一种基本的数据类型。编程语言可能会提供占据不同内存空间的整数类型，每种类型能表示的整数的范围也不相同。
Java中有4种不同的整数类型，分别为8位的byte(-2^7～2^7-1)、16位的short(-2^15～2^15-1)、32位的int(-2^31～2^31-1)和64位的long(-2^63～2^63-1)。 Java中的整数类型都是有符号整数，即如果整数的二进制表示的最高位为0则表示其为正数，如果整数的二进制表示的最高位为1则表示其为负数。
2. 整数知识扩展
a. 整数之二进制
- 整数在计算机中是以二进制的形式表示的。二进制是指数字的每位都是
0或1。例如，十进制形式的2转化为二进制形式之后是10，而十进制形式的10转换成二进制形式之后是1010。 - 位运算是把数字用二进制形式表示之后，对每位上
0或1的运算。二进制及其位运算是现代计算机学科的基石 - 位运算只有
6种：非、与、或、异或、左移和右移。非运算对整数的二进制按位取反，0取反得1，1取反得0。
| 运算名称 | 公式A | 公式B | 公式C | 公式D |
|---|---|---|---|---|
| 与(&) | 0&0=0 | 1&0=0 | 0&1=0 | 1&1=1 |
| 或( l ) | 0 l 0=0 | 1 l 0=1 | 0 l 1=1 | 1 l 1=1 |
| 非(^) | 0^0=0 | 1^0=1 | 0^1=1 | 1^1=0 |
（ps：由于|在表格中属于特殊符号，此处用I代替）
- 左移运算符
m<<n表示把m左移n位，左边丢弃，右边补0；右位移相反。
整数题目 | 二进制
题目一：前n个数字二进制形式中1的个数
输入一个非负数n，请计算0到n之间每个数字的二进制形式中1的个数，并输出一个数组。例如，输入的n为4，由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1，因此输出数组[0，1，1，2，1]。
题目分析
难度： ⭐
思路： 位运算可以使得程序更加的高效。通过i&(i-1)将整数i最右边的1变成0（如110，计算后变为100），直到其计算结果为0，在计算的过程中通过数组进行记录计算的次数，也就是1的个数。
参考代码
public static void method(int n) {
int [] result = new int[n + 1];
for (int i = 0; i <= n; i ++) {
int j = i;
while (j != 0) {
result[i]++;
j = j & (j - 1);
}
}
System.out.println(Arrays.toString(result));
}
Tips：2023-09-24 11:38
题目二：只出现一次的数字
输入一个整数数组，数组中只有一个数字出现了一次，而其他数字都出现了3次。请找出那个只出现一次的数字。例如，如果输入的数组为[0，1，0，1，0，1，100]，则只出现一次的数字是100。
题目分析
难度： ⭐⭐
思路： 出现3次的数二进制形式下的每一位按十进制进行累加计算，其结果一定是3的倍数。此时累加和对3求余，就能得到所求数当前二进制位上的值，最后通过位移运算进行累加可得结果。
参考代码
public static void method(int[] nums) {
int result = 0;
int[] bits = new int[32];
for (int num : nums) {
// 遍历对整数每一位进行累加
for (int i = 0; i < 32; i++) {
bits[31 - i] += num >> i & 1;
}
}
// 每一位对3求余，余数左移指定位，对结果累加
for (int i = 0; i < 32; i++) {
result += (bits[i] % 3) << (31 - i);
}
System.out.println(result);
}
Tips：2023-09-24 11:54
题目三：单词长度的最大乘积
输入一个字符串数组words，请计算不包含相同字符的两个字符串words[i]和words[j]的长度乘积的最大值。如果所有字符串都包含至少一个相同字符，那么返回0。假设字符串中只包含英文小写字母。例如，输入的字符串数组words为["abcw"，"foo"，"bar"，"fxyz"，"abcdef"]，数组中的字符串"bar"与"foo"没有相同的字符，它们长度的乘积为9。"abcw"与"fxyz"也没有相同的字符，它们长度的乘积为16，这是该数组不包含相同字符的一对字符串的长度乘积的最大值。
题目分析
难度： ⭐⭐
思路： 可以简单的通过数组boolean[][] = flag[words.length][26]记录每个单词中字母是否出现，再通过比对flag数组中指定位是否为true来判断是否存在相同字母；进一步优化，可以通过int[] = flag[words.length]记录存在标识（记录时可能用到或运算），每个元素为26位二进制的整数（如01000000000000000000000001表示包含字母b和z），比对时只需要进行与运算，结果为0则不存在相同字母。
参考代码
public static void method(String[] strArr) {
int arrLen = strArr.length;
int[] flag = new int[arrLen];
// 记录字符串的二进制形式
for (int i = 0; i < arrLen; i++) {
int len = strArr[i].length();
for (int j = 0; j < len; j++) {
flag[i] |= 1 << ('z' - strArr[i].charAt(j));
}
}
// 比对是否存在相同字母
int result = 0;
for (int i = 0; i < arrLen - 1; i++) {
for (int j = i + 1; j < arrLen; j++) {
// 不存在相同
if ((flag[i] & flag[j]) == 0) {
result = Math.max(result, strArr[i].length() * strArr[j].length());
}
}
}
System.out.println(result);
}
Tips：2023-09-24 12:06
二、数组
1. 数组基础知识
a. 数组相关概念
- 数组是一种简单的数据结构，是由相同类型的元素组成的数据集合，并且占据一块连续的内存并按照顺序存储数据。面试中出现的数组通常是一维或二维的。最简单的数组是一维的，其中元素的存取以单一的下标表示。二维数组对应于数学上矩阵的概念，其中元素的存取需要行和列两个下标。
- 创建数组时需要先指定数组的容量大小，然后根据容量大小分配内存。即使只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此，数组的空间效率不一定很高，可能会有空闲的区域没有得到充分利用。
- 为了解决数组空间效率不高的问题，人们又设计实现了动态数组，如Java中的ArrayList。动态数组既保留了数组时间效率高的特性，又能够在数组中不断添加新的元素。为了避免浪费，可以先为数 组分配较小的内存空间，然后在需要的时候在数组中添加新的数据。当数据的数目增加导致数组的容量不足时，需要重新分配一块更大的空间（通常新的容量是之前容量的2倍），把之前的数据复制到新的数组中，再把之前的内存释放。这样能减少内存的浪费，但每次扩充数 组容量时都有大量的额外操作，这对时间性能有负面影响。
2. 数组知识扩展
a. 数组中的双指针
- 双指针是一种常用的解题思路，可以使用两个相反方向或相同方 向的指针扫描数组从而达到解题目的。
- 方向相反的双指针经常用来求排序数组中的两个数字之和。
- 方向相同的双指针通常用来求正数数组中子数组的和或乘积。
数组题目 | 双指针
题目一：排序数组中的两个数字之和
输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。例如，输入数组[1，2，4，6，10]，k的值为8，数组中的数字2与6的和为8，它们的下标分别为1与3。
题目分析
难度： ⭐
思路： 双指针，定义左右指针，如果指针指向的值和小于预期，则左指针向右移动；否则右指针左移；其满足只使用一次的要求。
参考代码
public static void method(int[] arr, int sum) {
int len = arr.length;
for (int i = 0, j = len - 1; i <= j;) {
int res = arr[i] + arr[j];
if (res == sum) {
System.out.println(i + "---" + j);
break;
} else if (res > sum) {
j--;
} else {
i++;
}
}
}
Tips：2023-09-24 12:09
题目二：数组中和为0的3个数字
输入一个数组，如何找出数组中所有和为0的3个数字的三元组？需要注意的是，返回值中不得包含重复的三元组。例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们分别是[-1，0，1]和[-1，-1，2]。
题目分析
难度： ⭐⭐
思路： 题目意思为找出三个数，使得和为0，其可分解为两个步骤：第一步，对数组进行排序；第二步，指定一个元素数i，在剩余数组值中找到两个值和为-i。需要注意的是为了避免重复计算，对于定好的数i，如果下一个值和i相同则直接跳过。
复杂度： 排序算法Arrays.sort()的复杂度为O(nlogn)，找到符合条件的两个值的复杂度为O(n²)，综合复杂度为O(nlogn)+O(n²)。
参考代码
public static void method(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
int temp = nums[0];
for (int i = 0; i < len; i++) {
if (i != 0 && temp == nums[i]) {
continue;
} else {
temp = nums[i];
}
for (int j = i + 1, k = len - 1; j < k; ) {
int sum = nums[j] + nums[k] + nums[i];
if (sum == 0) {
System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
j++;
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
}
Tips：2023-09-26 22:51
题目三：和大于或等于k的最短子数组
输入一个正整数组成的数组和一个正整数k，请问数组中和大于或等于k的连续子数组的最短长度是多少？如果不存在所有数字之和大于或等于k的子数组，则返回0。例如，输入数组[5，1，4，3]，k的值为7，和大于或等于7的最短连续子数组是[4，3]，因此输出它的长度2。
题目分析
难度： ⭐
思路： 采用伸缩式滑块的形式来寻找，以左右指针定位滑块大小，滑块总和小于k则右伸，大于等于则左缩寻找更小的长度。
参考代码
public static void method(int[] nums, int k) {
int left = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (left <= right && sum >= total) {
min = Math.min(min, right - left + 1);
sum -= nums[left++];
}
}
System.out.println(min == Integer.MIN_VALUE ? 0 : min);
}
Tips：2023-09-27 22:57
题目四：乘积小于k的子数组
输入一个由正整数组成的数组和一个正整数k，请问数组中有多少个数字乘积小于k的连续子数组？例如，输入数组[10，5，2，6]，k的值为100，有8个子数组的所有数字的乘积小于100，它们分别是[10]、[5]、[2]、[6]、[10，5]、[5，2]、[2，6]和[5，2，6]。
题目分析
难度： ⭐
思路： 同上题。不同点在于每次满足小于100时，计数+1。
参考代码
public static void method(int[] nums, int k) {
int left = 0, count = 0;
long sum = 1;
for (int right = 0; right < nums.length; right++) {
sum *= nums[right];
while (left <= right && sum >= total) {
sum /= nums[left++];
}
count += right >= left ? right - left + 1 : 0;
}
System.out.println(count);
}
Tips：2023-10-09 20:03
b. 累加元素求子数组和
- 问题：使用双指针解决子数组之和的面试题有一个前提条件——数组中的所有数字都是正数。如果数组中的数字有正数、负数和零，那么双指针的思路并不适用。
- 换一种思路：假设整个数组的长度为n，它的某个子数组的第1个数字的下标是i，最后一个数字的下标是j。为了计算子数组之和，需要先做预处理，计算从数组下标为0的数字开始到以每个数字为结尾的子数组之和。预处理只需要从头到尾扫描一次，就能求出从下标0开始到下标0结束的子数组之和S0，从下标0开始到下标1结束的子数组之和S1，以此类推，直到求出从下标0开始到最后一个数字的子数组之和Sn-1。因此，从下标为i开始到下标为j结束的子数组的和就是Sj-Si-1。
数组题目 | 累加元素求子数组和
题目一：和为k的子数组
输入一个整数数组和一个整数k，请问数组中有多少个数字之和等于k的连续子数组？例如，输入数组[1，1，1]，k的值为2，有2个连续子数组之和等于2。
题目分析
难度： ⭐⭐
思路： 由于数组并未说明是正整数数组，所以双指针不适用。换一种思路，通过x - (x - k) = k的简单逻辑，记第i个元素的前项和（包括自己）为x，则题目转化为求第i个元素前有多少个元素的前项和（包括自己）为x - k，在遍历数组的过程中，我们可以通过hash(x, times)来记录前项和x出现的次数，同时借助该hash表统计子数组数量。
参考代码
Tips：2023-10-09 20:36
题目二：0和1个数相同的子数组
输入一个只包含0和1的数组，请问如何求0和1的个数相同的最长连续子数组的长度？例如，在数组[0，1，0]中有两个子数组包含相同个数的0和1，分别是[0，1]和[1，0]，它们的长度都是2，因此输出2。
题目分析
难度： ⭐⭐
思路： 上题的变形，和为固定值k转变为不定值(i + 1) / 2，在计算的时候用-1代替0，不定值就能变为定值0。
参考代码
Tips：2023-10-09 20:38
题目三：左右两边子数组的和相等
输入一个整数数组，如果一个数字左边的子数组的数字之和等于右边的子数组的数字之和，那么返回该数字的下标。如果存在多个这样的数字，则返回最左边一个数字的下标。如果不存在这样的数字，则返回-1。例如，在数组[1，7，3，6，2，9]中，下标为3的数字（值为6）的左边3个数字1、7、3的和与右边两个数字2和9的和相等，都是11，因此正确的输出值是3。
题目分析
难度： ⭐
思路： 元素左边元素和可以通过累加得到，右边元素和可以通过总和减去左边元素以及当前元素得到。
参考代码
public static void method(int[] nums) {
int total = 0;
for (int num : nums) {
total += num;
}
int len = nums.length, sum = 0;
for (int i = 0; i < len; i++) {
sum += nums[i];
// 左元素和等于右元素和，则找到符合条件的元素
if (sum - nums[i] == total - sum) {
System.out.println(i);
return;
}
}
System.out.println(-1);
}
Tips：2023-10-09 20:39
题目四：二维子矩阵的数字之和
输入一个二维矩阵，如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和？对于同一个二维矩阵，计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如，输入图1中的二维矩阵，以及左上角坐标为（2，1）和右下角坐标为（4，3）的子矩阵，该函数输出8。
题目分析
难度： ⭐️⭐️
思路： 对于矩阵(x, y) - (m, n)直接求解时，可通过起始点得到矩阵范围，遍历即可计算得出结果，复杂度为O(mn)。换一种思路，记点(0, 0)到点(x, y)所形成的矩阵元素和为sum(x, y)，子矩阵(x, y) - (m, n)的元素和可以拆解为sum(m, n) - sum(x, n) - sum(m, y) + sum(x, y)，为了提升每次求解时的速度，可以进行预计算，计算并存储每个点到(0, 0)所形成的矩阵的元素和，再通过上述公式计算得到最终结果。对于求解sum(x, y)，可以拆分为sum(x - 1, y)加上第x行从0到y -1下标的所有元素总和。
参考代码
Tips：2023-10-22 22:30
三、章节小结
整数在计算机中使用二进制形式表示，每位不是0就是1。位运算是对二进制整数的运算，包括与运算、或运算、非运算、异或运算、左移运算和右移运算。只有深刻理解每种位运算的特点才能在需要的时候灵活地应用合适的位运算解决相应的问题。
双指针是解决与数组相关的面试题的一种常用技术。如果数组是排序的，那么应用双指针技术就能够用O(n)的时间在数组中找出两个和为给定值的数字。如果数组中的所有数字都是整数，那么应用双指针技术就可以用O(1)的辅助空间找出和为给定值的子数组。
如果关于子数组的数字之和的面试题并没有限定数组中的所有数字都是正数，那么可以尝试从第1个数字开始累加数组中前面若干数字之和，两个累加的和的差值对应一个子数组的数字之和。这种累加数组中前面若干数字之和的思路，不仅适用于一维数组，还适用于二维数组。