11/14 11/15 LeetCode四道简单数组题：1480、1470、1512、1431、1486。
仅 《1512 好数对的数目》用到了 HashMap 要用一些脑子。
1480 一维数组的动态和 题目描述 给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。nums 的动态和。
1 2 3 输入：nums = [1,2,3,4] 输出：[1,3,6,10] 解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
1 2 3 输入：nums = [1,1,1,1,1] 输出：[1,2,3,4,5] 解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
1 2 输入：nums = [3,1,2,10,1] 输出：[3,4,6,16,17]
我的解答 1 2 3 4 5 6 7 8 9 10 class Solution public int [] runningSum(int [] nums) { int [] newArray = new int [nums.length]; newArray[0 ] = nums[0 ]; for (int i=1 ;i<nums.length;i++){ newArray[i] = newArray[i-1 ]+nums[i]; } return newArray; } }
扣友解答 1 2 3 4 5 6 7 8 9 10 11 class Solution public int [] runningSum(int [] nums) { for (int i=1 ;i<nums.length;i++){ nums[i]+=nums[i-1 ]; } return nums; } } 作者：fan-hua-4d 链接：https: 来源：力扣（LeetCode）
分析一波 仅修改当前数组的元素
即可，大道至简，执行效率差不多
1470 重新排列数组 题目描述 给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。
1 2 3 输入：nums = [2,5,1,3,4,7], n = 3 输出：[2,3,5,4,1,7] 解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
1 2 输入：nums = [1,2,3,4,4,3,2,1], n = 4 输出：[1,4,2,3,3,2,4,1]
1 2 输入：nums = [1,1,2,2], n = 2 输出：[1,2,1,2]
我的解答 1 2 3 4 5 6 7 8 9 10 class Solution public int [] shuffle(int [] nums, int n) { int [] nums2 = new int [2 *n]; for (int i=0 ;i<n;i++){ nums2[2 *i]=nums[i]; nums2[2 *i+1 ] = nums[n+i]; } return nums2; } }
扣友题解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution public int [] shuffle(int [] nums, int n) { int index = 0 ; int [] result = new int [nums.length]; for (int i = 0 ; i < n; i++) { result[index++] = nums[i]; result[index++] = nums[n+i]; } return result; } } 作者：diaoliwei 链接：https: 来源：力扣（LeetCode）
分析两波 数组插入和搜索效率极低，所以想到动态初始化一个新数组，按照索引，刷新元素值。时间复杂度为o(n)。
1512 好数对的数目 题目描述 给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
1 2 3 输入：nums = [1,2,3,1,1,3] 输出：4 解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
1 2 3 输入：nums = [1,1,1,1] 输出：6 解释：数组中的每组数字都是好数对
1 2 3 4 输入：nums = [1,2,3] 输出：0 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-good-pairs
1 Count how many times each number appears. If a number appears n times, then n * (n – 1) / 2 good pairs can be made with this number.
我的解答 最简单的暴力解法。时间复杂度O(n^2)，空间复杂度O(1)。
我简单的脑子和简单的知识面真只能想到这个。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution public int numIdenticalPairs (int [] nums) int re=0 ; for (int i=0 ;i<=nums.length-2 ;i++){ for (int j=i+1 ;j<=nums.length-1 ;j++){ if (nums[i]==nums[j]){ re++; } } } return re; } }
官方解答 时间复杂度O(n)，空间复杂度O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution public int numIdenticalPairs (int [] nums) Map<Integer, Integer> m = new HashMap<Integer, Integer>(); for (int num : nums) { m.put(num, m.getOrDefault(num, 0 ) + 1 ); } int ans = 0 ; for (Map.Entry<Integer, Integer> entry : m.entrySet()) { int v = entry.getValue(); ans += v * (v - 1 ) / 2 ; } return ans; } } 作者：LeetCode-Solution 链接：https:
扣友解答 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution public int numIdenticalPairs (int [] nums) int count=0 ; Map<Integer,Integer> map=new HashMap<>(); for (int num:nums){ int valve=map.getOrDefault(num,0 ); count+=valve; map.put(num,valve+1 ); } return count; } } 作者：czKI
分析三波 刷第一遍的前200道题，10分钟想不出来思路的直接可以放弃、去看解答。有思路，不用管复杂度，直接刚、暴力就暴力吧。
拿这题来说，看了官方的解答、我知道要用 hashmap，跑回去看了我 hashmap 做过的笔记，发现还是做不了，本质就是没有学 getOrDefault 这个可以统计重复次数的方法，思路有、实现不了。看完解答、再去搜帮助文档，可以基本理解。
官方解答：第一步，或者不重复元素作为键、重复次数作为值的 Map 集合，遍历map集合的值，计算其组合数之和。
扣友题解：一步到位，无需重新遍历新的map集合，奇技淫巧。
1431 拥有最多糖果的孩子 题目描述 给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。
1 2 输入：candies = [2,3,5,1,3], extraCandies = 3 输出：[true,true,true,false,true]
1 2 输入：candies = [4,2,1,1,2], extraCandies = 1 输出：[true,false,false,false,false]
1 2 输入：candies = [12,1,12], extraCandies = 10 输出：[true,false,true]
我的解答 先找出最多拥有糖果的孩子的糖果数量，再遍历判断，每个孩子的糖果加上分配的糖果是否大于该最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution public static List<Boolean> kidsWithCandies (int [] candies, int extraCandies) List<Boolean> l1 = new ArrayList<Boolean>(); int max = candies[0 ]; for (int i=0 ;i<=candies.length-1 ;i++){ if (candies[i]>max){ max=candies[i]; } } for (int j=0 ; j<=candies.length-1 ;j++){ if (candies[j]+extraCandies>=max){ l1.add(j, true ); }else { l1.add(j,false ); } } return l1; } }
官方解答 思路相同，时间复杂度O (n )，空间复杂度O (n1 )。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution public List<Boolean> kidsWithCandies (int [] candies, int extraCandies) int n = candies.length; int maxCandies = 0 ; for (int i = 0 ; i < n; ++i) { maxCandies = Math.max(maxCandies, candies[i]); } List<Boolean> ret = new ArrayList<Boolean>(); for (int i = 0 ; i < n; ++i) { ret.add(candies[i] + extraCandies >= maxCandies); } return ret; } } 作者：LeetCode-Solution
分析四波 好吧，是爷忘了还有 Math.max 这个函数，问题不大。问题出现我再告诉大家~
1486 数组异或操作 题目描述 给你两个整数，n 和 start 。
数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。
1 2 3 4 输入：n = 5, start = 0 输出：8 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。
1 2 3 4 输入：n = 4, start = 3 输出：8 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8. 来源：力扣（LeetCode）
我的解答 没什么脑子，就是一次循环，异或运算符 ^。
1 2 3 4 5 6 7 8 9 10 11 class Solution public int xorOperation (int n, int start) int [] nums = new int [n]; int re = 0 ; for (int i=0 ; i<=n-1 ;i++){ nums[i] = start +2 *i; re = re^nums[i]; } return re; } }
官方解答
时间复杂度：O(n)O (n )。这里用一重循环对 nn 个数字进行异或。
空间复杂度：O(1)O (1)。这里只是用了常量级别的辅助空间。
1 2 3 4 5 6 7 8 9 10 11 class Solution public int xorOperation (int n, int start) int ans = 0 ; for (int i = 0 ; i < n; ++i) { ans ^= (start + i * 2 ); } return ans; } } 作者：LeetCode-Solution
分析五波 题目说数组的异或运算，其实没有必要新建一个数组 int[] nums，直接用各个元素值进行运算就ok。