1.数组
一.一维数组动态和
1.题目描述：
给你一个数组 nums，请返回 nums 的动态和。
2.示例：
输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
3.解:
(1)我的答案：
class Solution {
public int[] runningSum(int[] nums) {
int[] nums_dy=new int[nums.length];
for(int i=nums.length-1;i>0;i--){
int s=nums[i];
for(int j=0;j<i;j++){
s +=nums[j];
}
nums_dy[i]=s;
}
nums_dy[0]=nums[0];
return nums_dy;
}
}(2)网友答案：
1.
class Solution {
public int[] runningSum(int[] nums) {
for(int i=1 ; i<nums.size(); ++i){
nums[i] +=nums[i-1];
}
return nums;
}
}2.
class Solution {
public int[] runningSum(int[] nums) {
int[] runningSum = new int[nums.length];
int tempSum = 0;
for(int i = 0 ; i < nums.length ; i++){
tempSum += nums[i];
runningSum[i] = tempSum;
}
return runningSum;
}
}4.总结：
网友答案2中，使用一个临时变量tempSum来记录数组中某个元素前面所有元素之和，省掉了一次循环，则省掉了创建变量j；减少了内存使用空间，也减少了代码执行次数。
二.好数对的数目
1.题目描述
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
2.示例
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
3.解：
(1)网友答案:
class Solution {
public int numIdenticalPairs(int[] nums) {
int[] cnt = new int[101];
int times = 0;
for(int num:nums){
times +=cnt[num];
cnt[num]++;
}
return times;
}
}4.总结：
网友的答案提示我们遇到问题思考其数学本质是什么，就可以拜托暴力求解的思维。那这道题目来举例，对于某个数字，这个数字的好数对的个数本质上是数学公式：n*(n+1)/2,也即1+2+...+(n-1)+n。所以数字num的个数每多一个，就代表其n+1,就代表1+2变成了1+2+3。所以答案里很巧妙的使用了times +=cnt[num];这相当于将每个数字的好数对个数求出来之后再求和。
三.数组中出现次数超过一半的数字
1.题目描述：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
2.示例：
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
3.解:
（1）我的答案：
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0;
int voteNum = 0;
for (int i = 0; i < nums.length; i++) {
if (voteNum == 0) candidate = nums[i];
if (candidate == nums[i]) voteNum++;
if (candidate != nums[i]) voteNum--;
}
return candidate;
}
}class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> times = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
times.put(nums[i], times.getOrDefault(nums[i], 0) + 1);
if (times.get(nums[i]) > nums.length / 2) return nums[i];
}
return 0;
}
}4.总结
第一个是摩尔投票法，最适合这个题，专门记住就行了。第二种是常规的使用哈希的方法，主要利用哈希可以根据key找到value的特点，记录每个元素出现的次数。
四.判断能否形成等差数列
1.题目描述：
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
2.示例：
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
3.解:
（1）我的答案：
import java.util.Arrays;
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
boolean a = false;
if(arr.length>=3){
if(canMakeArithmeticProgression(Arrays.copyOfRange(arr,0,arr.length-2))){
if(arr[arr.length-1]-arr[arr.length-2] == arr[arr.length-2]-arr[arr.length-3]) a=true;
else a=false;
}
}
else{
a=true;
}
return a;
}
}（2）网友答案：
import java.util.Arrays;
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
int d = arr[0] - arr[1];
for (int i = 1; i < arr.length - 1; i++)
if (d != arr[i] - arr[i + 1])
return false;
return true;
}
}4.总结：
网友的答案是比较正常的思路，先排序然后逐个判断。而我的答案之所以用递归是因为不熟练，需要多练习，这里用递归并不好，因为排序这个操作和创建那个boolean变量的操作只需要一次，而我这样写就重复执行了。
五.交换和
1.题目描述：
给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。
返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
2.示例：
输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]
3.解:
（1）我的答案：
class Solution {
public int[] findSwapValues(int[] array1, int[] array2) {
Set <Integer> set = new HashSet();
int sum1 = 0;
int sum2 = 0;
for (int i :array1){
sum1 += i;
}
for (int i :array2){
sum2 += i;
set.add(i);//对array2去重，使array2变成一个哈希set
}
int diff = sum1-sum2;//总差值
if(diff % 2 != 0){
return new int[]{};
}
for (int i :array1){
if(set.contains(i-diff/2)){
return new int[]{i,i-diff/2};
}
}
return new int[]{};
}
}4.总结：
本质还是两个for循环，但是直接两个for循环会超时的，所以利用set的元素不重复的特性，将一个数组转变成hashSet，对另一个数组进行for循环，每次判断set是否包含满足条件的元素，其实就是另一层循环。当然这个题也可以把两个数组都转换成set，效果应该更好。另外这两个数组的元素之和的差值必然是偶数才能满足题目条件，存在可以交换的元素，记住这个数学特性。
正浩创新EcoFlow公司福利 646人发布
