算法Day-8

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

本题求一个数组中三个不同下标的值相加等于0的三个值，并返回这三个数，不容许重复的三元组，但返回的值的顺序可以随意。

我们这题先将nums进行排序，以便后续进行去重操作，可以通过一个for循环加双指针的思想进行求解，通过for循环i值，获取三元组中第一个数，并判断nums[i]是否大于0，因为是排序之后的数组，如果num[i]还大于0，就说明后续也没有几个数相加等于0的可能，直接返回。然后就是去重i，当i>0,去比较i和他前一个i是否相等。如果相等就说明重复，跳出当前循环将i++。确定了第一个数的值，我们就开始取left = i+1和right  =数组最后一位的下标，只有当left<right时才进行循环，判断三个数的值=sum，如果sum>0就让right--，如果sum<0就让left++，因为排过序了，所以right在数组最后--之后值一定变小，同理left的值一定变大，当sum ==0时就将各个值添加到res中，并因为要对left和right去重，判断各自要移动的方向的值是否与现在的值相等，因为我们现在的值已经加入到res中，所以有相等的就要直接++变成相等的值，在最后将left++和right--；最后再返回res。

public class Solution {public IList<IList<int>> ThreeSum(int[] nums) {var res = new List<IList<int>>();Array.Sort(nums);for(int i = 0;i<nums.Length;i++){if(nums[i]>0){break;}if(i>0&&nums[i]==nums[i-1]){continue;}int left = i+1;int right = nums.Length-1;while(left<right){int sum = nums[i]+nums[left]+nums[right];if(sum>0){right--;}else if(sum<0){left++;}else{res.Add(new List<int>{nums[i],nums[left],nums[right]} );while(left<right&&nums[right]==nums[right-1]) right--;while(left<right&&nums[left]==nums[left+1]) left++;left++;right--;}}}return res;}
}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

本题和三数之和基本思想一致，但多了一个值并且，target不一定是0，可能小于零，在剪枝时不但要判断nums[k]否大于零，还要判断值是否大于target，这样判断就默认target是大于0的，因为如果target小于0，比如target为-5，而数组为[-2,-2,-1]这样如果只判断num[k]大于target就跳出循环，会导致结果有问题。然后再遍历i=k+1；再继续剪枝，但条件要变成nums[k]+nums[i]>0&&nums[k]+nums[i]>target，现在将k和i看作一个整体。然后在想三数之和一样去获取left和right的值，并去重。

public class Solution {public IList<IList<int>> FourSum(int[] nums, int target) {var res = new List<IList<int>>();Array.Sort(nums);for(int k = 0;k<nums.Length;k++){if(nums[k]>0&&nums[k]>target){break;}if(k>0&&nums[k]==nums[k-1]){continue;   }for(int i = k+1;i<nums.Length;i++){if(nums[k]+nums[i]>0&&nums[k]+nums[i]>target){break;}if(i>k+1&&nums[i]==nums[i-1]){continue;}int left = i+1;int right = nums.Length-1;while(left<right){int n1 = nums[left];int n2 = nums[right];int sum = nums[k]+nums[i]+n1+n2;if(sum>target){right--;}else if(sum<target){left++;}else{res.Add(new List<int>{nums[i],nums[k],n1,n2});while(left<right&&nums[right-1]==n2) right--;while(left<right&&nums[left+1]==n1) left++;right--;left++;}}}}return res;}
}

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

本题反转字符数组将hello->olleh的过程。

可以使用双指针的思想

声明两个int类型的left一个等于0，一个right等于数组最后下标，即数组的开头和结尾，进行循环交互首尾数值，直到left<right交换完毕。

public class Solution {public void ReverseString(char[] s) {int right = s.Length-1;int left = 0;while(left<right){char temp = s[right];s[right] = s[left];s[left] = temp;left++;right--;}}
}