反转字符串

link：344. 反转字符串 - 力扣（LeetCode）

思路分析

其实最开始学C语言的时候，也遇到过类似题目.当时自以为的投机取巧无非只是倒序打印而不是逆置元素.（hh 果然小白都会这样 当然也有更聪明的小懒狗直接用库函数 【及其不推荐】

双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while(left < right) {
          char tmp = s[left];
          s[left] = s[right];
          s[right] = tmp;
          right--;
          left++;
        }
    }
}

Tip

更优雅的处理方式——异或
因为a ^ a = 0,b ^ 0 =b
所以：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while(left < right) {
          s[left] ^= s[right];
          s[right] ^= s[left];
          s[left] ^= s[right];
          right--;
          left++;
        }
    }
}

第一步： s[left] ^= s[right];

  • 用 s[left] 与 s[right] 进行异或操作，并将结果存储在 s[left] 中。
  • 此时 s[left] 的值变为 A ^ B，而 s[right] 仍然是 B。

第二步： s[right] ^= s[left];

  • 将 s[right] 与更新后的 s[left] 进行异或操作，并将结果存储在 s[right] 中。
  • 因为 s[left] 是 A ^ B，所以 s[right] ^= (A ^ B) 相当于 B ^ (A ^ B)。
  • 由于 B ^ B = 0 和 0 ^ A = A，此时 s[right] 的值变为 A。

第三步： s[left] ^= s[right];

  • 将 s[left] 与更新后的 s[right] 进行异或操作，并将结果存储在 s[left] 中。
  • 因为 s[right] 是 A，所以 s[left] ^= A 相当于 (A ^ B) ^ A。
  • 由于 A ^ A = 0 和 0 ^ B = B，此时 s[left] 的值变为 B。

四数之和

link：18. 四数之和 - 力扣（LeetCode）

思路分析

本题大致思路和三数之和基本一致，只不过题目给出四个数字都互不相同且target是输入的并非0.
在三数之和的基础单独嵌套for循环即可.
**注意 **

当数组首元素大于0并且i下标位置的value大于target的时候就可以直接pass.
因为当target为负数但首元素比target大时就可能会忽略值.
例：target = -6 但nums[0] = -5
如果按照三数之和的去重条件会不符合预期【因为三数之和求解的target是0 元素都大于0 那三数加和自然不会为0】

1
if(nums[i] > 0)

去重a的逻辑相同 为了避免[1,1,2]这种情况 判断为

1
if(i > 0 && nums[i] == nums[i -1])

去重b的逻辑从i+1位置开始【其实相当于left】 和去重a一样的逻辑

1
if(j > i + 1 && nums[j - 1] == nums[j])
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //不用返回下标 双指针法先排好序
         List<List<Integer>> result = new ArrayList<>();
         Arrays.sort(nums);   

      for(int i = 0; i < nums.length; i++) {
         //nums[i] > target 剪枝操作
         if(nums[i] > 0 && nums[i] > target){
                return result;
         }
         //去重a
           if(i > 0 && nums[i - 1] == nums[i]) {
                    continue;
           }
           //去重b
            for(int j = i + 1; j < nums.length; j++) {
            if(j > i + 1 && nums[j - 1] == nums[j]) {
                continue;
            }
             int left = j + 1;
             int right = nums.length - 1;
             while(right > left) {
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                if(sum > target) {
                    right--;
                }else if(sum < target) {
                    left++;
                }else {
                    result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                    //去重d【就是right】
                    while(right > left && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    //去重c
                    while(right > left && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    left++;
                    right--;
                }
             }
          }
      }
        return result;
    }
}