代码随想录算法训练营第七天|454.四数相加II、383.赎金信 、15.三数之和 、18.四数之和

454.四数相加II

字典法：

public class Solution {
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Dictionary<int,int> dic=new Dictionary<int,int>();
    foreach(int a in nums1)
    {
        foreach(int b in nums2)
        {
            int sum=a+b;
            if(dic.ContainsKey(sum))
            {
                dic[sum]++;
            }else
            {
                dic.Add(sum,1);
            }
        }
    }
    int ans=0;
    foreach(int c in nums3)
    {
        foreach(int d in nums4)
        {
            int sum=c+d;
            if(dic.TryGetValue(-sum,out int result))
            {
                ans+=result;
            }
        }
    }
        return ans;
    }
}

383.赎金信

暴力法：

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        int cnt=0;
        int i=0;
        int k=0;
       for(i=0;i<magazine.Length;i++)
       {
           for(k=0;k<ransomNote.Length;k++){
            if(ransomNote[k]==magazine[i])
           {
               ransomNote=ransomNote.Remove(k,1);
                break;
           }
           }               
       }
      if(ransomNote=="")
               {
                   return true;
               }
        return false;
    }
}

15.三数之和

双指针：

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

18.四数之和

双指针：

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        var ans=new List<IList<int>>();
        for(int i=0;i<nums.Length-3;i++)
        {
            if (nums[i]>0&&nums[i]>target)
            {
                return ans;
            }
            int a=nums[i];
            if(i>0&&a==nums[i-1])
            {
                continue;
            }
            for(int j=i+1;j<nums.Length-2;j++)
            {
                int b=nums[j];
                if(j>i+1&&b==nums[j-1])
                {
                    continue;
                }
                int left=j+1;
                int right=nums.Length-1;
                while(left<right)
                {
                    int c=nums[left];
                    int d=nums[right];
                    if(a+b+c+d>target)
                    {
                        right--;
                    }else if(a+b+c+d<target)
                    {
                        left++;
                    }else
                    {
                        ans.Add(new List<int>{a,b,c,d});
                        while(left<right&&nums[left]==c)
                        {
                            left++;
                        }
                        while(left<right&&nums[right]==d)
                        {
                            right--;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

凌晨的夜真难熬。