1. 力扣Hot100系列18Java技巧篇解析作为刷过3000力扣题的Java老手我发现Hot100系列中技巧类题目往往最考验解题思维。这类题目不像数据结构题那样有固定套路需要灵活运用数学规律、位运算、双指针等技巧才能高效解决。今天我们就深入剖析这5道经典技巧题只出现一次的数字Single Number多数元素Majority Element颜色分类Sort Colors下一个排列Next Permutation寻找重复数Find the Duplicate Number这些题目在亚马逊、谷歌等大厂面试中出现频率极高掌握它们能显著提升算法思维水平。我将结合Java特性分享最优解法和避坑指南。2. 只出现一次的数字Single Number2.1 问题重述给定非空整数数组其中某个元素只出现一次其余每个元素均出现两次。要求找出那个只出现一次的元素。示例 输入[4,1,2,1,2] 输出42.2 位运算解法这是最经典的位运算应用题使用异或(XOR)运算可以O(n)时间复杂度、O(1)空间复杂度解决public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }原理分析异或运算特性a ^ 0 aa ^ a 0满足交换律和结合律由于重复数字异或后会抵消为0最终剩下的就是唯一数字注意这种解法仅适用于其他数字都出现两次的情况。如果改为出现三次则需要更复杂的位操作。2.3 变种问题如果数组中有两个只出现一次的数字解法会复杂些public int[] singleNumberIII(int[] nums) { int diff 0; for (int num : nums) diff ^ num; diff -diff; // 获取最右侧的1 int[] result new int[2]; for (int num : nums) { if ((num diff) 0) result[0] ^ num; else result[1] ^ num; } return result; }3. 多数元素Majority Element3.1 问题描述给定大小为n的数组找到出现次数超过⌊n/2⌋的元素假设总是存在。示例 输入[2,2,1,1,1,2,2] 输出23.2 摩尔投票法最优解法是Boyer-Moore投票算法时间复杂度O(n)空间O(1)public int majorityElement(int[] nums) { int count 0; Integer candidate null; for (int num : nums) { if (count 0) candidate num; count (num candidate) ? 1 : -1; } return candidate; }算法原理维护一个候选人和计数器遇到相同元素计数器1不同则-1当计数器归零时更换候选人由于多数元素占比过半最终剩下的必是它3.3 验证步骤虽然题目假设存在多数元素但实际面试时可能需要验证// 在返回前添加验证 count 0; for (int num : nums) if (num candidate) count; return count nums.length / 2 ? candidate : -1;4. 颜色分类Sort Colors4.1 问题说明给定包含0、1、2的数组原地进行排序荷兰国旗问题。示例 输入[2,0,2,1,1,0] 输出[0,0,1,1,2,2]4.2 三指针解法最优解使用三个指针一次遍历public void sortColors(int[] nums) { int low 0, high nums.length - 1; int curr 0; while (curr high) { if (nums[curr] 0) { swap(nums, curr, low); } else if (nums[curr] 2) { swap(nums, curr, high--); // 注意curr不增加 } else { curr; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }关键点low指针左侧全是0high指针右侧全是2curr指针遍历遇到1直接跳过遇到2交换后curr不前进因为交换来的元素可能为04.3 边界情况测试时需要特别注意全0或全1或全2的数组已经排序好的数组空数组虽然题目说非空5. 下一个排列Next Permutation5.1 题目理解实现获取数组下一个字典序排列的函数。如果已是最大排列则返回最小排列。示例 输入[1,2,3] 输出[1,3,2]5.2 算法步骤public void nextPermutation(int[] nums) { int i nums.length - 2; while (i 0 nums[i] nums[i 1]) i--; if (i 0) { int j nums.length - 1; while (j 0 nums[j] nums[i]) j--; swap(nums, i, j); } reverse(nums, i 1); } private void reverse(int[] nums, int start) { int end nums.length - 1; while (start end) swap(nums, start, end--); }步骤解析从后向前找第一个下降点inums[i] nums[i1]如果找到再从后向前找第一个大于nums[i]的数nums[j]交换nums[i]和nums[j]反转i1到末尾的部分5.3 常见错误忘记处理已经是最大排列的情况i-1时直接反转整个数组交换后没有正确反转后半部分边界条件处理不当数组长度1时6. 寻找重复数Find the Duplicate Number6.1 问题描述给定包含n1个整数的数组数字在1到n之间假设只有一个重复数找出它。示例 输入[1,3,4,2,2] 输出26.2 快慢指针法最优解将数组视为链表用Floyd判圈算法public int findDuplicate(int[] nums) { int slow nums[0]; int fast nums[0]; do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast); slow nums[0]; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; }算法原理将数组值视为指向下一个节点的指针重复元素会导致环路产生第一阶段找到快慢指针相遇点第二阶段找到环的入口点即重复元素6.3 其他解法对比方法时间复杂度空间复杂度是否修改原数组排序法O(nlogn)O(1)是哈希表O(n)O(n)否位运算O(nlogn)O(1)否快慢指针O(n)O(1)否7. 综合技巧总结7.1 位运算要点异或运算的消消乐特性利用掩码提取特定位注意Java中位运算的优先级最好多用括号7.2 双指针技巧对撞指针如颜色分类快慢指针如寻找重复数滑动窗口虽未在本篇出现但也是重要技巧7.3 原地操作技巧交换元素实现O(1)空间利用输入数组本身存储信息注意修改顺序避免覆盖在实际面试中解释清楚算法原理和trade-off比直接写代码更重要。建议先说明思路再写代码最后用测试案例验证。这些技巧类题目往往有多个解法能分析各解法优劣会大大加分。