The approach involves the following:

• Keeping a running sum of all the elements so far as we iterate through them
• If the running sum is equal to k, then we can increment the answer by 1 because then we have found a valid subarray that starts from index 0
• If there is a prefix sum for sum-k in the map, that means we can form sum = k
• This is because the prefix sum for sum subtracted by the the prefix sum for sum-k is k (sum - (sum-k) = k). This means that we can take all of the elements up to sum and subtract it by all of the elements up to sum-k to get k.
• Increase the value in the map for the current running sum

Explanation: we keep an accumulator variable sum with the running total of the sum of numbers; we then check if we have already met that values using our seen hashmap that acts more or less like a frequency table, storing how many times we have encountered a specific value: sum - k.

That is why if have met sum - k before and now the value is sum, the difference between those specific points and the current iteration is, by definiton, exactly k: we are now at sum, so, the interval between the previous point(s) and now sums up to, by definition, sum - (sum - k), which equates k.

We collect all those occurrences in count and finally we return it.

And apparently also the most advanced, reading the solution tab:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum=0; // calculated sum
        unordered_map<int, int> rec; // prefix sum recorder.
        int cnt = 0; // number of found subarray
        rec[0]++; // to take into account those subrrays that begin with index 0
        for(int i = 0; i<nums.size(); i++)
        {
            sum += nums[i];
            cnt += rec[sum-k];
            rec[sum]++;
        }
        return cnt;
    }
};

// sum : 1, 2, 3
// cnt : rec[1-2] = 0, rec[2-2] = 1, rec[3-2] = 2
// rec : rec[1] , rec[2], rec[3]

notation

Prefix sum : 어떤 데이터를 누적하여 합한것을 말한다.

• We are given range of numbers m to n. We are asked to find the bitwise and in the given range [m,n].
• A simple solution would be to go from m to n and do a bitwise and given as following:

int and=0;
for (m;m<=n;m++)
     {
	 and&=m;
	 }

But the solution is not effective and efficient for large range of numbers. So we use bit manipulations for solving this problem. Consider the case where range is given as [5,7]. The representation is given as following:

5 - 0101 6 - 0110 7 - 0111

since we are dealing with and(&) operator any presence of 0 with a 1 gives 0. We loop through the binary representation and in the lsbs of elements m and n if there is a 0 and a 1 then the resultant value is 0, so we shift the elements right till there are equal and count the increments made i.e for each of the shift till both the numbers become equal. When both elements m and n are equal we get the value in the lsb as 1. From the above binary representation of the numbers and range we make the following observations:

1. The third bit from lsb is common for all the three numbers in the range.
2. There are zeros in the first and second positions from the lsb so the resultant value will be 0 in that postion. Count is a variable wich keeps a track of number of zeros from the lsb to the case of m==n.

The code is as following

public:
    int rangeBitwiseAnd(int m, int n) {
         int count=0;
       // simple solution is to do bitwise and and return the sum.
      //     for(int i=m;i<=n;i++)
      //               sum&=i;        
		 //      return sum;
        while(m!=n)  // see till both numbers are equal
        {   // right shift both numbers by 1
            m>>=1;
            n>>=1;
            count++;  // increment the count.
        }
		//count gives the number of zero places from the lsb so left shift m by count.
        return m<<count;

        // count^(m)
    }

Right Shift & Left shift

https://www.geeksforgeeks.org/left-shift-right-shift-operators-c-cpp/

Another Explanation

https://gamjatwigim.tistory.com/158

• There is a similar example in Java, but I wanted to share my solution using the new C++11 unordered_map and a list. The good thing about lists is that iterators are never invalidated by modifiers (unless erasing the element itself). This way, we can store the iterator to the corresponding LRU queue in the values of the hash map. Since using erase on a list with an iterator takes constant time, all operations of the LRU cache run in constant time.

class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;
    } // LRUCache(int capacity) : size(capacity);

    int get(int key) {
        if(kv.count(key)==0)
            return -1;
        updateLRU(key);
        return kv[key];
    }

    void put(int key, int value) {
        if(kv.size() == size && kv.count(key) == 0)
        {
            evict();
        }
        updateLRU(key);
        kv[key] = value;

    }
    void updateLRU(int key)
    {
        if(kv.count(key))
        {
            LRU.erase(mp[key]);
        }
        LRU.push_front(key);
        mp[key] = LRU.begin();
    }
    void evict(){
        mp.erase(LRU.back());
        kv.erase(LRU.back());
        LRU.pop_back();
    }
private:
    int size;
    list<int> LRU; // MRU..LRU
    unordered_map<int, list<int>::iterator> mp; //key-> iterator
    unordered_map<int, int> kv; // key->value


};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

• Bottom-up DP utilizes a matrix m where we track LCS sizes for each combination of i and j.

• If a[i] == b[j], LCS for i and j would be 1 plus LCS till the i-1 and j-1 indexes.
• Otherwise, we will take the largest LCS if we skip a charracter from one of the string (max(m[i - 1][j], m[i][j - 1]).
• This picture shows the populated matrix for “xabccde”, “ace” test case.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<short>> m(text1.size()+1,vector<short>(text2.size()+1));
        for(auto i = 1; i<=text1.size();i++)
        {
            for(auto j=1; j<=text2.size();j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    m[i][j] = m[i-1][j-1]+1;
                }
                else
                {
                    m[i][j] = max(m[i-1][j],m[i][j-1]);
                }
            }
        }
        return m[text1.size()][text2.size()];
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i = 0;
        int n = nums.size();
        for(int reach = 0; i<n && i<=reach; i++)
        {
            reach = max(i + nums[i], reach);
        }
        return i == n;

    }
};

• I just iterate and update the maximal index that I can reach
• from index 0 to n-1, update max reach at each iteration. If successfully iterate through, i would match n. Exit condition is when i<=reach fails, i.e. fail to reach this index i, for loop quits. This is an early stopping, so i hasn’t incremented enough to match n yet, meaning fail to reach n.
• “reach” means how far you can go from the starting point. The question changes to “Can you reach the ending point from the starting point?” Here, starting point is index=0, ending point is index=array.length-1. That’s the reason why we do “i+A[i]”. Our view is always starting from index=0.