目录
四数相加2（Leetcode454）
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int cnt = 0; //用来计数
Map<Integer,Integer> map = new HashMap();
/*
* 这一步用来存 数组1和数组2里面值的和,然后再用来和数组3和数组4和的值进行比较，如果相加为0则满足条件
* a+b+c+d=0 我们先将a+b的值还有出现次数存起来
* 这里要注意值的合可以重复，所以不去重
*/
//这里是求a+b和的个数
for(int i = 0;i<nums1.length;i++) {
for(int j = 0;j<nums2.length;j++) {
int temp = nums1[i]+nums2[j];//求两个数组的值
map.put(temp, map.getOrDefault(temp, 0)+1); //存temp出现的次数,默认为0,之前存过则+1;
}
}
//这里求0-(c+d)=temp,求map中是否有满足a+b=temp 有的话需要加上次数。
for(int i = 0;i<nums3.length;i++) {
for(int j = 0;j<nums4.length;j++) {
int temp = nums3[i]+nums4[j];
if(map.get(0-temp)!=null) { //map中找是否有和0减去数组3和数组4之后相等的值
cnt+=map.get(0-temp);
}
}
}
return cnt;
}赎金信（Leetcode383）
//1、统计magazine里面有多种字符，每种字符的个数
//2、遍历ransomNode,若是magazine里面的值为0，则代表没有或者不够用，返回false
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
for(int i = 0;i<magazine.length();i++) {
arr[magazine.charAt(i)-97]++;
}
for(int i = 0;i<ransomNote.length();i++) {
arr[ransomNote.charAt(i)-97]--; //magazine里面匹配一次就减1
if(arr[ransomNote.charAt(i)-97]<0) { //减完要判断是否小于0，小于0代表magazine里面缺少字符
return false;
}
}
return true;
}三数之和 （Leetcode15）
/*
* 注意点：每个三元组下标不重复，但是不同元组下标可以重复，只要和为0即可
* 存的是不同坐标下的值，而不是坐标
*/
//直接提交第一个函数就可以了
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
//quickSort(nums,0,nums.length-1);
Arrays.sort(nums); //先排序，方便指针还有减枝操作
for(int i = 0;i<nums.length;i++) { //遍历每个i
if(nums[i]>0) { //如果nums[i]>0,因为是从小到大排，如果最小的数都大于0,后面的数相加也必定大于0
return result;
}
if(i>0&&nums[i]==nums[i-1]) { //去重,这里如果是用nums[i]==nums[i+1]的话会去掉[-1,-1,2]的情况，i>0防止为空
continue;
}
int left = i+1;
int right = nums.length-1;
while(right>left) { //如果right>=left 相当于出现存在一个坐标对应的值被取了2次的情况
if(nums[i]+nums[left]+nums[right]>0) { //>0证明和太大，所以right--,让和变小
right--;
}else if(nums[i]+nums[left]+nums[right]<0) {//<0证明和太小，所以left++,让和变大
left++;
}else {
result.add(Arrays.asList(nums[i],nums[left],nums[right])); //Arrays.asList:将多个数组成数组
while(right>left&&nums[right]==nums[right-1]) right--; //还可以继续寻找，去除重复值
while(right>left&&nums[left]==nums[left+1]) left++;
left++;
right--;
}
}
}
return result;
}
//快排
public static void quickSort(int[] nums,int l,int r) {
while(l<r) {
int p1 = l;
int p2 = r;
int temp = nums[l];
while(p1<p2) {
if(nums[p2]<temp) { //p2找比temp小的 p2先找
if(nums[p1]>temp) { //p1找比temp大的
int flag = nums[p2];
nums[p2] = nums[p1];
nums[p1] = flag;
}else {
p1++;
}
}else {
p2--;
}
}
nums[l] = nums[p1];
nums[p1] = temp;
quickSort(nums,l,p1); //分段再排
quickSort(nums,p1+1,r); //分段再排
}
}四数之和（Leetcode18）
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int a = 0;a<nums.length;a++) {
if(nums[a]>0&&nums[a]>target) { //这里要注意大于0
return result;
}
if(a>0&&nums[a]==nums[a-1]) { //与三数之和一样去重
continue;
}
for(int b = a+1;b<nums.length;b++) {
if(nums[a]+nums[b]>=0&&nums[a]+nums[b]>target){//这里要break不能return 例如[-3,-2,-1,0,0,1,2,3] target=0 当a指向-1,b指向3时return的话会缺少-1,0,0,1
break;
}
if(b>a+1&&nums[b]==nums[b-1]){ //与三数之和一样去重
continue;
}
int c = b+1;
int d = nums.length-1;
while(c<d) {
if(nums[a]+nums[b]+nums[c]+nums[d]<target) {
c++;
}else if(nums[a]+nums[b]+nums[c]+nums[d]>target) {
d--;
}else {
result.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
while(c<d&&nums[c]==nums[c+1]) c++;
while(c<d&&nums[d]==nums[d-1]) d--;
c++;
d--;
}
}
}
}
return result;
}反转字符串（Leetcode344）
//值得注意的是原地修改数组，不能多开数组
public void reverseString(char[] s) {
int l = 0;
int r = s.length-1;
while(l<r) {
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}反转字符串2（Leetcode541）
//条件一 每计数2k则反转前k个
//条件二 剩余少于k则全部反转
//条件三 小于2k但是大于等于k,反转前k个
//其实条件1和3可以合成一个条件，每次反转k个,
public String reverseStr(String s, int k) {
char[] result = s.toCharArray();
int i = 0;
while(i<result.length) {
int end = Math.min(result.length-1, i+k-1); //其实每次就去判断在一个区间内是否可以反转k个，若是没办法的话则全部反转，也这时也就是在末尾了
swapStr(result,i,end);
i += 2*k;
}
return new String(result);
}
//直接在数组上交换
public void swapStr(char[] arr,int start,int end) {
while(start<end) {
char temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}}
