• 1.两数之和


    1.两数之和 原题链接

    题解

    在数组中找到一组数组使得他们的和为目标值,最容易想到的方式是暴力的做法,直接利用两个循环

    代码如下:

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            int n=nums.size();
            int i,j;
            for(i=0;i<n-1;++i){
                for(j=i+1;j<n;++j)
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            } 
            return{i,j};
        }  
    };
    

    上述的方法的时间复杂度为O(n^2),时间复杂度较高,因此我们可以优化内层循环,使用哈希表的方式

    代码如下:

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            if(nums.size() == 0) return {};
            unordered_map<int, int> m;
    
            for(int i = 0; i < nums.size(); ++i){
                int t = target - nums[i];
                if(m.count(t)) return {i, m[t]};
                m[nums[i]] = i;
            }
    
            return {};
        }
    };
    

    上述的哈希表的方式,只要不存在大量的哈希冲突(一般也不会存在,除非题目故意卡你),查找和插入的时间复杂度近似为常数级,所以时间复杂度为O(N)

    来个Java版本的

    class Solution {
        public int[] twoSum(int[] nums, int target) {
            int len = nums.length;
            if(len == 0) return null;
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < len; ++i){
                int t = target - nums[i];
                if(map.get(t) != null) return new int[]{map.get(t), i};
                map.put(nums[i], i);
            }
            return null;
        }
    }
    
  • 相关阅读:
    虚拟机的Linux 安装 若干问题(一)
    理解JavaScript的闭包
    javascript里面的引用类型和值类型
    javascript导入自定义模块
    简单了解下CAP定理与BASE定理
    背包问题之完全背包
    背包问题之多重背包
    背包问题之0-1背包
    搜索算法初步总结
    谈一谈“回溯法“
  • 原文地址:https://www.cnblogs.com/Lngstart/p/13202524.html
一二三 - 开发者的网上家园