LeetCode-数组

//从数组两端开始遍历
//时间复杂度O（n^2）
//对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,耗时O(1)
//空间复杂度：O（1）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int head=0;head<nums.length-1;head++ )
        {
            for(int tail=nums.length-1;tail>head;tail--)
            {
                if(nums[head]+nums[tail]==target){
                    return new int[]{head,tail};
                }
            }
        }
		return new int[]{};
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap();
        for(int i=0;i<nums.length;i++) {
            //用目标值减数组元素，查看map中是否有这个键
            if(map.containsKey(target-nums[i]))
                return new int[]{i,map.get(target-nums[i])};
            map.put(nums[i],i);
        }
        return new int[]{};
    }
}
//第一次target=9，target-2=7，map中没有这个键，把值和索引装入map中，形成（2：0）
//第二次target-7=2，map中有2这个键，返回i和键2所对应的的值[0,1]

利用双指针遍历数组

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length<=0) {
            return 0;
        }
        int mov=0; //赋值指针指针
        int res=1; //统计不重复元素的个数
        for(int i=0;i<nums.length;i++) { //i相当于移动指针
            if(nums[mov]==nums[i]) {
                continue; //两个指针从数组第一个元素开始比较，如果相同，跳过本次循环
            }else {
                mov++; //当两个指针指的位置元素不相等就表示是一个新元素
                nums[mov]=nums[i]; //把赋值指针向后移动一位，把新元素赋值给赋值指针位置
                res++; //元素个数加一
            }
        }
        return res;
    }
}

public int removeElement(int[] nums, int val) {
    	//如果数组中没有元素或者数组中只有一个元素且元素是要删除的元素，返回0
		if(nums.length<=0 || (nums.length==1 && nums[0]==val)) {
			return 0;
		}
		int res=0;//记录复合条件的元素个数
		int preres=0;//记录排序后待删除元素之前元素的个数
		int head=0;
    	//先对给定的数组进行从小到大排序
		for(int i=0;i<nums.length-1;i++) {
			for(int j=i+1;j<nums.length;j++) {
				if(nums[i]>nums[j]) {
					int merge=nums[i];
					nums[i]=nums[j];
					nums[j]=merge;
				}
			}
		}
    	//查找要删除元素在数组中的第一个位置，赋值给head
		for(int i=0;i<nums.length;i++) {
			if(nums[i]==val) {
				head=i;
				preres=i;
				break;
			}
		}
    	//从head索引开始，把后边不需要删除的元素前移
		for(int i=head;i<nums.length;i++) {
			if(nums[i]!=val) {
				int merge=nums[head];
				nums[head]=nums[i];
				nums[i]=merge;
				res++;
				head++;
			}
		}
		return res+preres;
        
    }

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}
/*
我们可以保留两个指针 i 和 j，其中 i 是慢指针，j 是快指针。
当nums[j] 与给定的值相等时，递增j以跳过该元素。只要 nums[j]!=val，我们就复制nums[j]到nums[i] 并同时递增两个索引。重复这一过程，直到j到达数组的末尾，该数组的新长度为i。
*/
//时间复杂度：O(n)， 假设数组总共有n个元素，i和j至少遍历2n步。
//空间复杂度：O(1)

class Solution {
    public int searchInsert(int[] nums, int target) {
        //遍历数组，如果有目标值，返回索引位置
        for(int i=0;i<nums.length;i++) {
            if(nums[i]==target)
                return i;
        }
        //如果数组中没有目标值
        for(int j=0;j<nums.length;j++) {
            //如果J位置的元素大于目标值，那就应该把目标值放在J的位置
            if(nums[j]>target) {
                return j;
            }
        }
        //否则把目标值放到最后
        return nums.length;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
    	//假设最大和为第一个数
        int max = nums[0];
        //定义一个存储累加和的容器，赋值为0
        int res = 0;
        int length = nums.length;
        //遍历数组
        for (int i = 0;i < length;i++) {
            //累加
            res += nums[i];
            //如果累加的和比第i个数还小，则把第i个数作为当前最大和
            if (nums[i] > res) {
                res = nums[i];
            }
            //用比较函数求两个数的最大值
            max = Math.max(max,res);
            /*
            和数学函数等效代替，但是数学函数更快
            if(res>max) {
            	max=res;
            }
            */
        }
        return max;
    }
}

class Solution {
    public int[] plusOne(int[] digits) {
        //数组最后一位数执行加一操作
		digits[digits.length-1]=digits[digits.length-1]+1;
        //从数组最后一位，也就是个位数开始，检测是否大于等于10了
        for(int i=digits.length-1;i>=0;i--) {
            //如果是最高位的数大于等于10
        	if(i==0 && digits[i]>=10) {
                //把当前位重置为零
        		digits[i]=0;
                //新建一个比原来数组容积大一的新数组
        		int[] newdigits=new int[digits.length+1];
                //新数组的最高位为1
        		newdigits[0]=1;
                //把旧数组的元素转移到新数组，从新数组的第二个位置开始
        		for(int j=0;j<digits.length;j++) {
        			newdigits[j+1]=digits[j];
        		}
                //返回新数组
        		return newdigits;
        	}//如果不是最高位大于等于10
        	else if(digits[i]>=10 && i!=0) {
                //把当前位数字重置为零，高一位的数字执行加一操作
        		digits[i]=0;
        		digits[i-1]++;
        	}
        }
		return digits;
    }
}