LeetCode day22

LeetCode day22

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

---

一开始想着能不能正则，但是发现整型数组不太行。。。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer>set=new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        return nums.length-set.size()!=0;
    }
}

嘛，排序再遍历就不写了。

主要是我以为int转Integer数组嘎嘎容易

---

1480. 一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

---

啊？你说这个我可不困了啊，最开始饱受dp折磨，现在已经敏感起来了。

class Solution {
    public int[] runningSum(int[] nums) {
        int len=nums.length;
        int[]dp=new int[len];
        dp[0]=nums[0];
        for(int i=1;i<len;i++){
            dp[i]=dp[i-1]+nums[i];
        }
        return dp;
    }
}

---

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"]

---

不额外分配的话,那就直接原地交换呗？直接双索引解决

class Solution {
    public void reverseString(char[] s) {
        int front;
        int tear;
        for(front=0,tear=s.length-1;front<=tear;front++,tear--){
            char temp=s[front];
            s[front]=s[tear];
            s[tear]=temp;
        }
    }
}

---

LCR 006. 两数之和 II - 输入有序数组

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值*。*numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：

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

---

直接暴力？这也太。。。。

class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int front=0;
            int tail=0;
            for( front=0;front<numbers.length-1;front++){
                for(tail=numbers.length-1;tail>front;tail--){
                    if(numbers[front]+numbers[tail]==target){
                        return new int[]{front,tail};
                    }
                    if(numbers[front]+numbers[tail]<target){
                        break;
                    }
                }
            }
            return new int[]{front,tail};//凑数
        }
    }

感觉纯暴力肯定过不了，这个提前跳出都够呛了

class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int front=0;
            int tail=numbers.length-1;
            while(front<=tail){
                int sum=numbers[front]+numbers[tail];
                if(sum==target) return new int[]{front,tail};
                else if (sum<target) front++;
                else tail--;
            }
            return new int[]{front,tail};
        }
}

---

害。。一直在想，这个升序怎么去做文章，这个直接两边慢慢收缩就好了啊